이진 탐색 — 알고리즘, 시간 복잡도와 코드

이진 탐색은 정렬된 리스트에서 목표값을 빠르게 찾는 방법입니다. 가운데 항목을 확인하고, 남은 값의 절반을 제외한 뒤, 이 과정을 반복합니다. 리스트가 정렬되어 있지 않다면 이 논리는 성립하지 않습니다.

오름차순 리스트에서는 규칙이 간단합니다. 가운데 값이 목표값보다 작으면 오른쪽을 탐색하고, 크면 왼쪽을 탐색합니다. 범위가 계속 절반 정도로 줄어들기 때문에 이진 탐색의 시간 복잡도는 $O(\log n)$입니다.

정렬된 리스트에서 이진 탐색이 동작하는 방식

다음 정렬된 리스트를 사용해 봅시다:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

목표값이 $31$이라고 가정해 봅시다.

처음에는 전체 범위에서 시작합니다. 가운데 값은 $24$입니다. $31 > 24$이므로 $24$의 왼쪽에 있는 값들은 모두 제외할 수 있습니다. 따라서 탐색은 다음 범위에서 계속됩니다.

$$[31, 39, 45, 52]$$

이제 가운데 값은 $39$입니다. $31 < 39$이므로 $39$의 오른쪽에 있는 값들은 모두 제외할 수 있습니다. 그러면 범위는 다음과 같이 됩니다.

$$[31]$$

이제 가운데 값이 $31$이므로 탐색을 멈춥니다. 중요한 점은 단지 목표값을 찾았다는 것만이 아닙니다. 비교 두 번 만에 후보 범위가 $9$개의 값에서 $1$개로 줄어들었습니다.

왜 이진 탐색은 $O(\log n)$인가

비교할 때마다 남아 있는 후보의 절반 정도를 제거합니다. 한 번 진행하면 약 $n/2$개의 항목이 남고, 두 번 진행하면 약 $n/4$개가 남습니다. $k$번 진행한 뒤 남는 크기는 대략

$$\frac{n}{2^k}$$

입니다.

이 값이 대략 $1$이 되면 탐색이 끝나므로, 단계 수는 다음을 만족합니다.

$$2^k \approx n$$

양변에 $\log_2$를 취하면

$$k \approx \log_2 n$$

을 얻습니다.

이것이 이진 탐색이 규모가 커져도 효율적인 이유입니다. 선형 탐색은 최대 $n$번까지 확인해야 할 수 있지만, 이진 탐색은 범위를 계속 절반으로 줄이는 데 필요한 만큼만 확인하면 됩니다.

이진 탐색 코드 예제

다음은 Python으로 작성한 표준 반복문 버전입니다: