이진 탐색

이진 탐색은 사전에서 단어를 찾는 방법과 같습니다. 가운데를 펼쳐 단어가 그 앞인지 뒤인지 보고, 그 절반에서 반복합니다. 정렬된 목록이라면 백만 개의 값 중 어떤 값이든 최대 20번의 비교로 찾습니다.

정렬된 막대 한 줄. 가운데 막대가 강조되고, 줄의 절반이 흐려져 있으며, 목표 높이에 점선이 그어져 있다
정렬된 막대 한 줄. 가운데 막대가 강조되고, 줄의 절반이 흐려져 있으며, 목표 높이에 점선이 그어져 있다

기본 아이디어

정렬된 목록에서는 비교 한 번으로 목표값을 찾았는지뿐 아니라 목표값이 어느 쪽에 있는지도 알 수 있습니다. 목표값을 가운데 값과 비교합니다. 같으면 끝입니다. 가운데 값이 더 작으면 그 앞의 값도 모두 더 작으므로 목표값은 그 뒤에만 있을 수 있습니다. 더 크면 목표값은 그 앞에만 있을 수 있습니다. 그 절반만 남기고 반복합니다.

예시

2, 5, 8, 12, 16, 23, 38, 56, 72, 91에서 23을 찾습니다. 가운데 값은 16으로 더 작으므로 23부터 91까지만 남습니다. 그 가운데는 56으로 더 크므로 23과 38만 남습니다. 그 가운데는 23입니다. 비교 3번 만에 6번째 자리에서 찾았고, 선형 탐색은 6번이 필요합니다. 같은 목록에서 40을 찾으면 16, 56, 23, 38과 비교한 뒤 아무것도 남지 않습니다. 비교 4번으로 40이 없다는 것을 알 수 있고, 선형 탐색은 10번이 필요합니다.

절반씩 줄이면 금방 줄어든다

비교 한 번 뒤에는 최대 절반, 두 번 뒤에는 4분의 1, k번 뒤에는 최대 약 n/2ᵏ이 남습니다. 탐색은 아무것도 남지 않으면 멈추므로 비교는 최대 ⌊log₂ n⌋ + 1번입니다. 값 40개는 6번, 1,000개는 10번, 백만 개는 20번, 10억 개는 30번입니다. 목록이 두 배가 되어도 비교는 한 번만 늘어납니다. 이를 O(log n)이라고 씁니다.

설명은 쉽지만 제대로 짜기는 어렵다

John Mauchly는 1946년에 이진 탐색을 설명했지만, Donald Knuth에 따르면 모든 목록 길이에서 제대로 동작하는 첫 버전은 1962년에야 발표되었습니다. 이후 Jon Bentley는 전문 프로그래머 중 약 10명에 1명만 이를 올바르게 작성한다는 사실을 발견했습니다. 종료 조건과 절반으로 나눌 때의 플러스 1, 마이너스 1을 틀리기 쉽기 때문입니다. 2006년 Joshua Bloch는 가운데를 구하는 흔한 방법인 (low + high) / 2가 아주 긴 목록에서 오버플로할 수 있음을 보였습니다. 이 버그는 Java 라이브러리에 수년간 남아 있었습니다. 이 앱처럼 low + (high − low) / 2로 쓰면 피할 수 있습니다.

미 육군 사진. ENIAC 앞에 선 ENIAC 관계자들로, 왼쪽에서 다섯 번째가 존 모클리다. 모클리는 1946년에 이진 탐색을 설명했다.
미 육군 사진. ENIAC 앞에 선 ENIAC 관계자들로, 왼쪽에서 다섯 번째가 존 모클리다. 모클리는 1946년에 이진 탐색을 설명했다.

변형과 활용

중복된 값이 있으면 이진 탐색은 일치하는 값 중 하나를 찾습니다. 왼쪽이나 오른쪽으로 계속 탐색하는 버전은 첫 번째나 마지막 값, 또는 없는 값을 삽입할 자리를 찾습니다. 같은 절반 나누기 아이디어로 방정식의 근을 구하고(이분법), 버그가 처음 생긴 버전을 찾고(git bisect), 많은 최적화 퍼즐의 답을 구할 수 있습니다. 이진 탐색 트리는 모든 조회가 같은 절반 나누기 경로를 따르도록 데이터를 저장합니다.

직접 해 보기

앱을 열고 ‘찾을 값’에서 값을 고른 뒤 ‘단계’를 누르세요. 음영 부분은 목표값이 아직 있을 수 있는 범위입니다. 가운데 값이 강조되고, 제외된 절반은 흐려집니다. 타일에는 아직 후보로 남은 값의 개수와, 같은 값을 선형 탐색으로 찾을 때 필요한 비교 횟수가 표시됩니다. 목록에 없는 값을 찾거나 막대를 40개로 늘려 차이가 커지는 것을 확인해 보세요.

자주 묻는 질문

이진 탐색의 시간 복잡도는?

O(log n)입니다. 값 n개에 대해 비교는 최대 ⌊log₂ n⌋ + 1번입니다. 최선의 경우는 목표값이 가운데에 있을 때로, 비교 한 번입니다. 반복문 버전은 추가 메모리가 O(1)입니다.

이진 탐색과 선형 탐색의 차이는?

선형 탐색은 값을 차례로 하나씩 확인하며 어떤 목록에서도 동작하지만, 비교가 n번 필요할 수 있습니다. 이진 탐색은 정렬된 목록에서만 동작하지만, 비교할 때마다 남은 부분의 절반을 제외하므로 약 log₂ n번이면 됩니다.

이진 탐색을 쓰려고 목록을 정렬할 가치가 있나요?

여러 번 탐색할 때만 그렇습니다. 정렬에는 약 n log n 단계가 걸려 선형 탐색 한 번보다 많습니다. 일단 정렬하면 그 뒤의 탐색은 모두 매우 저렴합니다.

이진 탐색을 목록이 아닌 것에도 쓸 수 있나요?

네. 어떤 검사로 답의 어느 쪽에 있는지 알 수 있다면 무엇에든 쓸 수 있습니다. 숫자 범위, 프로그램의 버전, 업다운 숫자 맞히기 게임의 추측 등이 그렇습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

이진 탐색 해 보기