이진탐색법(Binary Search)

0. 개요

배열 안에서 특정 숫자를 찾는다고 해보자. 우리는 지금까지 for문을 사용하여 배열의 길이만큼 비교 함수를 반복해왔다. 1000개의 숫자 속에서 999를 찾으려면 999번 함수가 돌아야하는 셈이다. 이를 더 빠르고 효율적으로 찾기 위한 방법 중 하나로 이진탐색법을 소개한다.

1. 발상

① 배열은 무조건 오름차순으로 존재한다는 가정하에 진행된다.
② 배열의 정중앙 값을 골라 내가 찾는 숫자인지를 비교한다.
③ 만약 찾는 숫자가 이보다 작다면 중앙을 기준으로 왼쪽 배열 속에서 다시 중앙 값을 고른다.
④ 반대로 중앙 값보다 크다면? 오른쪽 배열 속에서 중앙 값을 고르면 된다.
⑤ 이렇게 점점 비교 영역을 절반씩 줄여나간다.

2. 구체적 예시

이 배열 속에서 9의 위치를 찾는다고 해보자.
정중앙을 기준으로 9는 오른쪽에 위치한다.
이제 영역은 5에서 12로 줄어든다.

이번에는 정중앙 값이 9와 동일하다.
9의 위치를 반환하고 함수를 종료하면 된다.
이전처럼 for문을 5번 돌아야 찾을 수 있었던 값을 단 두 번만에 찾아냈다.

3. 함수

const search = (nums, target) => {
  let low = 0;
  let high = nums.length - 1;
  
  while(high - low > 1) {
    let mid = low + Math.ceil((high - low) / 2);
    if(nums[mid] == target) {
      return mid;
    } else if(nums[mid] > target) {
      high = mid;
    } else {
      low = mid;
    }
  }
  
  // 마지막 남은 배열조각이 홀수라면 상관없지만
  // 짝수라면 같은 자리를 맴돌기 때문에
  // 아래와 같이 한번 처리해준다.
  
  if(nums[low] == target) return low;
  if(nums[high] == target) return high;
  
  return -1; //없을 경우
}