이진 탐색(Binary Search) 구현하기 with Javascript

이진탐색이란 정렬된 리스트에서 범위를 절반씩 좁혀가며 특정한 값을 찾아내기 위한 알고리즘이다.

탐색 범위를 절반씩 줄여나가는 방식으로 시간 복잡도는 O(log N)이다. 이는 순차 탐색보다 훨씩 빠르다.

 

이진 탐색 방식은 다음과 같다.

우선 배열이 정렬되어 있어야한다. (오름/내림차순 상관없지만 여기선 오름차순으로 설명한다)

찾고자 하는 값이 target일때, 배열의 중간에 위치한 값과 비교한다.

target이 중간 위치 값보다 작다면 중간값의 좌측 배열을 범위로 지정하고 해당 범위의 중간 위치 값과 비교한다.

반대로, target이 중간 위치 값보다 크다면 중간값의 우측 배열을 범위로 해당 범위의 중간 위치 값과 비교한다.

이 과정을 반복하여 target과 일치하는 값을 찾았을 때 Index를 리턴한다.

이를 코드로 구현하면 아래와 같다

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    // 중간 위치 값 지정
    let mid = Math.floor((left + right) / 2); 
    
    if (arr[mid] === target) {
      // Target과 일치할 경우 해당 index 리턴
      return mid;                             
    } else if (arr[mid] < target) {
      // 우측 배열 대상으로 범위 재지정
      left = mid + 1;                         
    } else {
      // 좌측 배열 대상으로 범위 재지정
      right = mid - 1;                        
    }
  }
  
  // 없으면 -1 리턴
  return -1;
}