이진 탐색(Binary Search): 정렬된 데이터에서 원하는 값을 찾는 효율적인 비결

도서관에서 책을 찾거나 사전에서 단어를 찾을 때, 우리는 본능적으로 처음부터 한 장씩 넘기지 않습니다. 대충 중간쯤을 펼쳐보고, 찾는 단어가 그보다 뒤에 있으면 뒷부분의 중간을, 앞에 있으면 앞부분의 중간을 다시 펼쳐봅니다. 이처럼 범위를 절반씩 뚝뚝 잘라내며 순식간에 데이터를 찾아내는 직관적인 방법, 바로 이진 탐색(Binary Search)입니다. 데이터가 40억 개라도 단 32번 만에 원하는 값을 찾아내는 이 놀라운 알고리즘의 원리와 구현 방법을 깊이 있게 파헤쳐 보겠습니다.

1. 이진 탐색이란? (Divide and Conquer)

이진 탐색은 정렬된 데이터 내에서 특정한 값을 찾을 때, 탐색 범위를 매 단계마다 절반($1/2$)으로 줄여가며 찾는 알고리즘입니다. '분할 정복(Divide and Conquer)' 전략의 가장 대표적인 예시입니다.

1-1. 필수 전제 조건: 정렬(Sorting)

이진 탐색을 사용하기 위해서는 반드시 지켜야 할 철칙이 있습니다. "데이터가 순서대로 정렬되어 있어야 한다"는 점입니다. 뒤죽박죽 섞인 데이터에서는 "중간값보다 크면 오른쪽으로 간다"는 논리가 성립하지 않기 때문입니다. 따라서 데이터가 자주 변하지 않고 고정된 상태에서 검색만 많이 하는 상황에 최적화되어 있습니다.

2. 동작 원리: 3개의 포인터

이진 탐색은 세 개의 위치 포인터를 사용하여 범위를 좁혀 나갑니다.

Start (Low): 탐색 범위의 시작 인덱스
End (High): 탐색 범위의 끝 인덱스
Mid: Start와 End의 중간 지점 `(Start + End) / 2`

2-1. 단계별 시뮬레이션

오름차순 정렬된 배열 `[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]`에서 숫자 `23`을 찾는 과정입니다. 1. 1단계: 전체 범위(0~9번 인덱스)의 중간인 `16`(4번 인덱스)을 봅니다. - 찾는 값 `23`이 `16`보다 큽니다. - 따라서 `16`보다 왼쪽에 있는 절반은 버립니다. (볼 필요가 없음) 2. 2단계: 남은 오른쪽 절반(5~9번 인덱스)에서 다시 중간을 봅니다. 3. 반복: 값을 찾거나(Success), 더 이상 줄일 범위가 없을 때(Fail)까지 반복합니다.

3. 시간 복잡도 증명: 왜 O(log N)인가?

이진 탐색의 속도는 수학적으로 증명 가능합니다. 데이터 개수 $N$을 탐색할 때마다 2로 나누는 과정이기 때문입니다. - 1회 차: $N$ - 2회 차: $N/2$ - 3회 차: $N/4$ - ... - k회 차: $N/2^k = 1$ (데이터가 1개 남음)

이 식을 정리하면 $2^k = N$이 되고, 양변에 로그를 취하면 $k = \log_2 N$이 됩니다. 즉, 데이터가 1,000개($2^{10}$)라면 약 10번, 100만 개($2^{20}$)라면 약 20번, 40억 개($2^{32}$)라면 약 32번의 비교만으로 충분합니다. 선형 탐색($O(N)$)과는 차원이 다른 속도입니다.

4. 실제 코드 구현 (JavaScript 예시)

이진 탐색은 재귀나 반복문으로 구현할 수 있으며, 코딩 테스트에서는 주로 반복문 방식을 선호합니다.


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

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);

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

주의할 점은 `while`문의 조건이 `start <= end`여야 한다는 것입니다. 등호를 빼먹으면 마지막 한 개가 남았을 때 검사하지 않고 종료되는 버그가 발생할 수 있습니다.

[핵심 요약]
1. 이진 탐색은 범위를 절반씩 좁혀가는 방식으로, 대용량 데이터에서 압도적인 성능(O(log N))을 냅니다.
2. 반드시 데이터가 정렬(Sorted)되어 있어야만 사용할 수 있다는 제약 조건이 있습니다.
3. Start, End, Mid 세 개의 포인터를 조작하여 구현하며, 경계 조건(`<=`) 처리에 유의해야 합니다.

kguidebook0001 님의 블로그