[Algorithm] 이진 탐색 및 변형 알고리즘 Binary Search Algorithm

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

 

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

 

💡 이진 탐색은 이분 탐색이라고도 불린다.

 

 

이진 탐색 기본

---

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

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

 

 

이진 탐색 응용

---

💡 bisect는 “이등분하다”라는 뜻으로 어떤 것을 두 부분으로 나누는 것을 의미한다.

 

파이썬에선 정렬된 리스트를 다루기 위해 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과 같거나 큰 요소의 모든 개수를 계산할 수 있다.

const countGreaterOrEqual = (sortedArr, target) => {
  const leftIndex = bisectLeft(sortedArr, target);
  return sortedArr.length - leftIndex; // target보다 크거나 같은 요소의 수
};

const arr = [1, 2, 4, 4, 6];
console.log(countGreaterOrEqual(arr, 4)); // 3

 

target이 4일 때 bisect_left는 2를 반환하고, target과 같거나 큰 요소의 모든 개수는 5-2=3이다

 

bisect_right (우측 이분 탐색)

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

const bisectRight = (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(bisectRight(arr, 4)); // 4
console.log(bisectRight(arr, 3)); // 2

 

오름차순 정렬된 배열이라면 bisect_right 함수가 반환한 인덱스 이전에 있는 요소들은 모두 target과 같거나 작다. 예를 들어 bisect_right가 4를 반환했다면 0~3 인덱스에 있는 요소는 target과 같거나 작은 값들이다. 따라서 bisect_right가 반환하는 인덱스는 곧 target과 같거나 작은 요소의 개수와 같다.

const countLessOrEqual = (sortedArr, target) => {
  return bisectRight(sortedArr, target);
};

const arr = [1, 2, 4, 4, 6];
console.log(countLessOrEqual(arr, 4)); // 4

 

target이 4일 때 bisect_right는 4를 반환하고, 이는 곧 target과 같거나 작은 모든 요소의 개수와 같다

 

---

글 수정사항은 노션 페이지에 가장 빠르게 반영됩니다. 링크를 참고해 주세요