이분 탐색은 정렬된 배열이나 리스트에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 전체 데이터를 순차적으로 탐색하는 대신, 탐색 범위를 절반씩 줄여나가는 방식으로 동작한다.
이 알고리즘의 핵심은 분할 정복전략에 있다. 매 단계마다 중간값을 기준으로 탐색 범위를 절반으로 나누고, 찾고자 하는 값이 어느 쪽 구간에 있는지 판단하여 불필요한 절반을 제거한다.
시간 복잡도는 $O(\log N)$으로, 데이터의 크기가 $N$일 때 최대 $\log_2 N$번의 비교만으로 원하는 값을 찾을 수 있다. 예를 들어, 전 세계 모든 사람(약 $2^{33}$명)이 가위바위보 토너먼트를 한다면, 우승자를 가리기 위해 한 사람당 대략 $\log_2(2^{33}) \approx 33$번의 대결만 필요하다. 만약 80억 명이라면 약 $\log_2(8 \times 10^9) \approx 33$번이면 충분하다. 이는 이분 탐색의 로그 시간 복잡도가 얼마나 효율적인지를 보여주는 직관적인 예시이다.
이분 탐색이 작동하기 위한 필수 조건은 데이터가 정렬되어 있어야 한다는 것이다. 정렬되지 않은 데이터에서는 중간값을 기준으로 한 판단이 불가능하므로, 반드시 사전에 정렬 작업이 선행되어야 한다.
이분 탐색은 크게 네 가지 핵심 개념으로 구성된다: 탐색 공간, 중간값, 결정, 그리고 종료 조건이다. 각 단계를 구체적인 예시와 함께 살펴보자.
탐색 공간은 해가 존재할 수 있는 모든 가능한 값들의 범위를 의미한다. 배열에서의 이분 탐색에서는 인덱스 범위 [Left, Right]가 탐색 공간이 된다.
탐색 공간의 핵심 특징:
예시: 정렬된 배열 [1, 3, 5, 7, 9, 11, 13]에서 값 7을 찾는다고 가정하자.
중간값은 현재 탐색 공간을 둘로 나누는 기준점이다. 이 값을 기준으로 어느 쪽 절반을 탐색할지 결정한다.
계산 방법:
Mid = Left + (Right - Left) // 2
또는 더 직관적으로:
Mid = (Left + Right) // 2
(주의: 큰 수에서는 오버플로우 방지를 위해 첫 번째 방법을 권장)
예시 - 1단계:
중간값은 항상 현재 탐색 공간의 중앙에 위치하므로 어느 쪽을 선택하더라도 탐색 공간이 대략 절반으로 줄어든다는 것이 보장된다.
결정 단계는 중간값 arr[Mid]와 찾고자 하는 목표값 Target을 비교하여, 다음에 어느 구간을 탐색할지 결정하는 과정이다. 이 단계에서 세 가지 경우가 발생할 수 있다.