이진 탐색 알고리즘은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 이진 탐색은 값의 크기에 따라 탐색 범위를 절반으로 줄여가며 원하는 값을 찾아내는 방식으로 작동하기 때문에 시간 복잡도는 $O(\log n)$으로 효율적이다. 예를 들어 1024개 요소를 가진 배열에서 원하는 값을 찾을 때 최대 10번의 비교만 필요하다.

하지만 데이터가 자주 변경된다면 매번 정렬을 해줘야 하기 때문에 효율성이 떨어질 수 있다. 데이터 삽입/삭제가 빈번한 경우엔 해시 테이블 같은 자료구조를 사용하는게 더 나을 수 있다.

<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 이진 탐색은 이분 탐색이라고도 불린다

</aside>

이진 탐색 기본

이진 탐색 과정을 시각화한 이미지

중앙값 계산
- 배열의 중간 인덱스를 계산한다 mid = Math.floor((left + right) / 2)
- 중앙값과 찾고자 하는 값(target)을 비교한다
값 비교 및 범위 조정
1. 반복 종료
  1. 중앙값이 찾고자 하는 값과 같다면 탐색을 종료하고 해당 인덱스를 반환한다
  2. 더 이상 탐색 범위가 없으면(left > right) 반복을 종료하고 -1을 반환한다
2. 계속 반복
  1. 중앙값이 찾고자 하는 값보다 작다면, 탐색 범위를 오른쪽 절반으로 줄인다 left = mid + 1
  2. 중앙값이 찾고자 하는 값보다 크다면, 탐색 범위를 왼쪽 절반으로 줄인다 right = mid - 1

const binarySearch = (sortedArr, target) => {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // 중앙 인덱스 계산

    if (sortedArr[mid] === target) return mid; // 원하는 값을 찾았을 때

    if (sortedArr[mid] < target) left = mid + 1; // 탐색 범위 오른쪽 절반으로 축소
    else right = mid - 1; // 탐색 범위 왼쪽 절반으로 축소
  }

  return -1; // 찾고자 하는 값이 없을 때
};

이진 탐색 응용

<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> bisect는 “이등분하다”라는 뜻으로 어떤 것을 두 부분으로 나누는 것을 의미한다.

</aside>

파이썬에선 정렬된 리스트를 다루기 위해 bisect라는 모듈을 제공한다. 이 모듈엔 정렬된 배열에서 특정 값이 들어갈 수 있는 위치를 찾을 때 사용하는 bisect_left, bisect_right 함수가 포함되어 있다. 자바스크립트에서도 이진 탐색 로직을 살짝만 변형해서 동일하게 구현할 수 있다.

bisect_left, bisect_right 작동 과정을 시각화한 이미지. 리스트에서 target과 같은 숫자는 *로 표시해뒀다

bisect_left (좌측 이분 탐색)

정렬된 배열에서 target을 삽입할 수 있는 가장 왼쪽 위치(인덱스)를 반환한다. target과 동일한 값이 1개 혹은 여러 개 존재하면, 가장 왼쪽에 있는 target의 위치를 반환한다. target과 동일한 값이 없다면, target보다 큰 값이 처음 나타난 위치를 반환한다.

const bisectLeft = (sortedArr, target) => {
  let left = 0;
  let right = sortedArr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
};

const arr = [1, 2, 4, 4, 6];

console.log(bisectLeft(arr, 4)); // 2
console.log(bisectLeft(arr, 3)); // 2

오름차순 정렬된 배열이라면 bisect_left 함수가 반환한 인덱스 이후에 있는 요소들은 모두 target과 같거나 크다고 볼 수 있다. 이를 활용하여 배열에서 target과 같거나 큰 요소의 모든 개수를 계산할 수 있다.