이진 탐색(Binary Search)

1.이진 탐색(Binary Search) 이란?

• 이진 탐색 알고리즘(Binary Search Algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다.

• 오름차순으로 정렬된 리스트의 중간 값을 임의의 값으로 선택하여, 찾고자 하는 Key값과 비교하는 방식으로 돌아가는 알고리즘 입니다.

• 정렬된 리스트에서만 사용할 수 있다는 단점이 존재합니다.

• 검색이 될때마다 선형탐색(Linear Search)와는 비교할 수 없게 빨라집니다.

출처: https://blockdmask.tistory.com/167 [개발자 지망생]

2. 이진 탐색의 시간 복잡도

• log2n입니다.

3. 이진 탐색의 구현

3.1 반복문으로 구현

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let low = 0
  let high = arr.length - 1
  let mid 

  while(low <= high){
    mid = Math.ceil((low + high) / 2)
    
    if(arr[mid] === target){
      return mid
    }else if (arr[mid] > target){
      high = mid - 1
    }else if (arr[mid] < target){
      low = mid + 1
    }
  }
  return -1 
};

3.2 재귀함수로 구현

const binarySearch = function (arr, target) {
  // TODO : 여기에 코드를 작성합니다.
  let low = 0
  let high = arr.length - 1
  let mid 

  while(low <= high){
    mid = Math.ceil((low + high) / 2)
    
    if(arr[mid] === target){
      return mid
    }else if (arr[mid] > target){
      return binarySearch(arr.slice(low, mid) ,target)
    }else if (arr[mid] < target){
      return binarySearch(arr.slice(mid, high), target)
    }

  }
  return -1 

};

• Test Case 는 통과했으나 아래와 같은 오류 발생

Test Result
  AssertionError: expected 3 to be 999229
      at Assertion.fail (/node_modules/should/cjs/should.js:275:17)
      at Assertion.value (/node_modules/should/cjs/should.js:356:19)
      at Context.<anonymous> (/submission/index.test.js:50:42)
      at processImmediate (internal/timers.js:456:21) ... 

Test Code
  function () {
      for (let i = 0; i < 3000; i++) {
        const offset = parseInt(Math.random() * 1000) + 1;
        const idx = size - offset;
        binarySearch(arr, arr[idx]).should.equal(idx);
      }
    }

• Size 라는 변수에 대해서 확인이 안됨.