[Algorithm] 이진 탐색(Binary Search) 이해하기

들어가며

코딩 테스트 문제를 풀다 보면 정답은 맞는 것 같은데 시간 초과가 나는 경우가 있습니다.

이럴 때 가장 먼저 의심해볼 수 있는 부분이 탐색 방식입니다.

배열을 처음부터 끝까지 확인하는 선형 탐색은 이해하기 쉽지만, 데이터가 많아지면 느려질 수 있습니다.

이때 정렬된 데이터라면 이진 탐색을 사용할 수 있습니다.

---

이진 탐색이란?

이진 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 알고리즘입니다.

핵심은 매번 가운데 값을 확인하고, 찾는 값이 어느 쪽에 있는지 판단해서 탐색 범위를 절반씩 줄이는 것입니다.

예를 들어 [1, 3, 5, 7, 9]에서 7을 찾는다고 해볼게요.

1. 가운데 값 5를 확인합니다.
2. 7은 5보다 크므로 오른쪽 절반만 확인합니다.
3. 오른쪽 범위에서 다시 가운데 값을 확인합니다.
4. 7을 찾으면 탐색을 종료합니다.

---

중요한 조건

이진 탐색을 사용하려면 데이터가 반드시 정렬되어 있어야 합니다.

const numbers = [1, 3, 5, 7, 9, 11];

정렬되어 있지 않은 배열에서는 가운데 값을 기준으로 왼쪽과 오른쪽을 버릴 수 없기 때문에 이진 탐색이 동작하지 않습니다.

---

시간 복잡도

선형 탐색은 최악의 경우 모든 요소를 확인해야 합니다.

O(n)

이진 탐색은 탐색 범위를 계속 절반으로 줄입니다.

O(log n)

데이터가 1,000,000개여도 이진 탐색은 약 20번 정도의 비교로 값을 찾을 수 있습니다.

이 차이 때문에 큰 데이터에서는 이진 탐색이 매우 강력합니다.

---

JavaScript 구현

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

  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);

    if (arr[mid] === target) {
      return mid;
    }

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];

console.log(binarySearch(numbers, 7)); // 6
console.log(binarySearch(numbers, 10)); // -1

값을 찾으면 해당 인덱스를 반환하고, 찾지 못하면 -1을 반환합니다.

---

코드 흐름 이해하기

left는 현재 탐색 범위의 시작 인덱스입니다.

right는 현재 탐색 범위의 끝 인덱스입니다.

mid는 두 값의 가운데 인덱스입니다.

arr[mid]가 찾는 값보다 작으면 왼쪽 범위는 더 이상 볼 필요가 없으므로 left = mid + 1로 이동합니다.

반대로 arr[mid]가 찾는 값보다 크면 오른쪽 범위를 버리고 right = mid - 1로 이동합니다.

---

마무리

이진 탐색은 정렬된 배열에서 값을 빠르게 찾을 수 있는 대표적인 알고리즘입니다.

핵심은 가운데 값을 기준으로 탐색 범위를 절반씩 줄이는 것입니다.

정렬되어 있다는 조건만 만족한다면, 큰 데이터에서도 훨씬 효율적으로 원하는 값을 찾을 수 있습니다.