이진 탐색(Binary Search)이 빠른 이유 (반으로 쪼개기)

앞서 우리는 선형 탐색과 이진 탐색의 속도를 비교하며, 이진 탐색이 40억 개의 데이터에서도 단 32번 만에 답을 찾아낸다는 놀라운 사실을 확인했습니다. 그렇다면 도대체 어떤 마법 같은 원리로 이런 속도가 가능한 것일까요? 단순히 "반으로 쪼갠다"는 말로는 부족합니다. 이번 글에서는 이진 탐색 알고리즘의 내부 구현 로직(코드)과, 왜 하필이면 시간 복잡도가 O(log n)이 되는지에 대한 수학적 배경을 깊이 있게, 하지만 아주 쉽게 파헤쳐 보겠습니다.

1. 이진 탐색의 핵심 로직: 3개의 포인터

이진 탐색을 코드로 구현하려면 3개의 화살표(포인터)가 필요합니다. - Low (Start): 탐색 범위의 맨 처음 인덱스 - High (End): 탐색 범위의 맨 마지막 인덱스 - Mid: Low와 High의 딱 중간 지점 인덱스

1-1. 알고리즘 수행 과정

우리가 오름차순으로 정렬된 배열 `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`에서 숫자 `23`을 찾는다고 가정해 봅시다.

초기화: Low=0번지(값 2), High=9번지(값 91)를 가리킵니다.
중간 찾기: Mid는 (0+9)/2 = 4.5, 즉 4번 인덱스(값 16)를 찍습니다.
비교 및 범위 축소:
- 찾는 값(23)이 중간 값(16)보다 큰가요? 네, 큽니다.
- 그렇다면 16보다 왼쪽에 있는 작은 수들은 볼 필요가 없습니다.
- Low를 Mid + 1 위치(5번지)로 옮깁니다. (범위가 절반 날아감)
반복: 이제 5번지~9번지 사이에서 다시 Mid를 찍고 위 과정을 반복합니다.

이 과정을 통해 매 단계마다 탐색 범위가 정확히 절반씩 줄어들게 됩니다.

2. 왜 시간 복잡도가 O(log n)일까?

이진 탐색의 속도를 수학적으로 증명하는 것은 생각보다 간단합니다. 데이터 개수 $N$을 계속 2로 나누는 과정이기 때문입니다.

1단계: $N$
2단계: $N / 2$
3단계: $N / 4$
...
k단계: $N / 2^k = 1$ (데이터가 1개 남을 때 종료)

결국 $2^k = N$이 되는 $k$(횟수)를 구하는 것이며, 양변에 로그를 취하면 $k = \log_2 N$이 됩니다. 그래서 데이터가 1,024개일 때($2^{10}$), 최악의 경우라도 딱 10번만 비교하면 답이 나오는 것입니다.

3. 실제 코드 구현 (JavaScript / Python)

이진 탐색은 라이브러리를 쓰기도 하지만, 코딩 테스트에서는 직접 구현해야 할 때가 많습니다. 가장 기본적인 반복문 형태입니다.


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

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

        if (arr[mid] === target) {
            return mid; // 찾았다! 인덱스 반환
        } else if (arr[mid] < target) {
            low = mid + 1; // 타겟이 더 크니까 오른쪽으로 이동
        } else {
            high = mid - 1; // 타겟이 더 작으니까 왼쪽으로 이동
        }
    }
    return -1; // 못 찾음
}

여기서 주의할 점은 `while (low <= high)` 조건입니다. 등호(`=`)를 빼먹으면 마지막 한 개가 남았을 때 검사를 안 하고 종료되는 버그가 발생할 수 있습니다.

4. 이진 탐색의 전제 조건: 정렬(Sorting)

이 강력한 알고리즘을 쓰기 위해서는 반드시 데이터가 정렬되어 있어야 한다는 대전제가 필요합니다. 정렬되지 않은 뒤죽박죽인 데이터에서는 "중간보다 크면 오른쪽"이라는 논리가 통하지 않기 때문입니다. 따라서 데이터가 자주 바뀌는 상황보다는, 고정된 데이터에서 검색만 많이 하는 상황에 최적화된 알고리즘입니다.

[핵심 요약]
1. 이진 탐색은 Low, High, Mid 세 포인터를 이용해 범위를 절반씩 좁혀가는 알고리즘입니다.
2. 매 단계마다 탐색 범위가 1/2로 줄어들므로 O(log n)이라는 압도적인 속도를 자랑합니다.
3. 반드시 데이터가 오름차순 등으로 정렬되어 있어야만 사용할 수 있다는 제약이 있습니다.

tech-korea