이진탐색 알고리즘 구현하시오,

정수 요소로 이루어진 배열(오름차순 정렬되어있음)과 찾고자 하는 수를 입력받아 그 수의 인덱스를 리턴하라. 수가 없을 경우 -1을 리턴할 것.

시간복잡도는 반드시 O(logN)을 준수할것.

내가 작성한 코드:

초기에 혼자서 재귀로 구현하려다 잘 안되어서 결국 노션에 정리해둔 것으로 인덱스 구함. 아래 코드는 엣지케이스까지 커버 가능하다.

//오름차순으로 정렬된 배열을 기준으로 한다. 
function binarySearch(sortedArray, seekElement) {
  let startIndex = 0;
  let endIndex = sortedArray.length - 1;

  while (startIndex <= endIndex) { //더 이상 배열을 절반으로 나눌 수 없을 때까지 반복한다.
    *const middleIndex = Math.floor((endIndex + startIndex) / 2);
    if (sortedArray[middleIndex] === seekElement) {
      return middleIndex; //해당 요소가 존재시 바로 리턴.
    }
    if (sortedArray[middleIndex] < seekElement) {
      startIndex = middleIndex + 1; //찾는 값이 middle보다 더 큰 경우 검색범위를 middle 이상으로 하기
    } else {
      endIndex = middleIndex - 1;
    }
  }

  return -1; //해당 요소가 배열에 없을 시 -1을 리턴한다.
}

재귀를 이용한 방법은 아래와 같이 인자 2개를 더 필요로 한다.

function BSearchRecursive(arr,target,low, high) {
    if (low > high)
        return -1;

    let mid = Math.floor((low + high) / 2);
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}

만약에, 그냥 존재 유무만 판단하려 한다면 다음과 같은 코드 작성이 가능하다.

helper 함수와 불 값을 할당하는 변수를 별도로 선언함으로써 bool 값이 false가 “리턴”되는 상황을 방지하였다.

function binary(arr,target){

  let hasTarget = false;

  (function helper(arr,target){
    let middleIdx = Math.floor(arr.length / 2);
    let middle = arr[middleIdx];

    //길이가 1인데 타겟이랑 값이 다르다. 그럼 false. 
    if(middle !== target) hasTarget = false;
    //어떤 길이든 무관하게 같으면. 트루.
    if(middle === target) {
      hasTarget = true;
      if(hasTarget) return true;
    }

    // if(middle !== target) 이고 길이가 1이 아닐 때. 더 나눌 수 있다. 
    if(middle > target){
      return helper(arr.slice(0,middleIdx),target);
    }
    if(middle < target){
      return helper(arr.slice(middle + 1),target);
    }
  })(arr,target);

  return hasTarget;
}