이진 탐색(Binary search)

사전에서 낱말을 찾을 때 첫 쪽부터 넘기는 사람은 없습니다. 아무 데나 펼쳐서 찾는 낱말이 그보다 앞인지 뒤인지 보고, 한쪽을 통째로 버립니다. 이진 탐색은 이것을 가장 규칙적으로 한 것입니다. 정렬된 목록의 한가운데 값과 찾는 값을 비교하고, 찾는 값이 있을 수 없는 절반을 버리기를 되풀이합니다.

아래는 크기순으로 늘어놓은 31개의 수입니다. 찾는 수는 입니다(분홍 선). 새 목록

처음부터 하나씩 보는 순차 탐색이었다면 번 비교했을 것입니다.

여기서 비교 한 번은 가운데 값과 견주어 '같다, 작다, 크다'를 한꺼번에 가리는 것으로 셉니다. 비교 한 번에 남은 후보가 절반 이하로 줄어드니, n개가 하나가 되기까지는 $\log_2 n$번쯤 걸립니다. 정확히는 많아야 $\lceil \log_2 (n+1) \rceil$번입니다(위의 식). 31개면 많아야 5번, 백만 개면 20번, 10억 개면 30번입니다. 목록이 $10^m$개, $m =$ 이면 이진 탐색은 많아야 번, 순차 탐색은 최악의 경우 번 비교합니다. 로그와 그 역인 지수의 차이, 점근 표기법⁠(asymptotic notation)⁠으로 말하면 $O(\log n)$과 $O(n)$의 차이입니다.

'같다'로 끝나는 마지막 한 번을 빼면, 비교 한 번의 답은 '앞' 아니면 '뒤', 곧 1비트입니다. 그래서 이진 탐색은 찾는 자리의 번호를 이진수로 한 자리씩 알아내는 것과 같습니다. 거꾸로, n개 가운데 하나를 가리키려면 적어도 $\log_2 n$비트가 필요하므로(엔트로피⁠, entropy⁠), 비교만으로 찾는 어떤 방법도 최악의 경우 이보다 크게 줄일 수는 없습니다. 이진 탐색은 이 한계에 거의 딱 맞습니다. 같은 셈이 비교 정렬의 하한⁠(comparison sorting lower bound)⁠을 줍니다.

이진 탐색의 조건은 목록이 먼저 정렬되어 있어야 한다는 것입니다. 정렬에는 이진 탐색보다 훨씬 많은 일이 드니, 여러 번 찾을 때에야 정렬에 한 번 투자할 만합니다. 순서는 필요 없고 같은 것만 찾으면 된다면 해시 테이블⁠(hash table)⁠이 평균⁠(mean)⁠ 상수 번의 비교로 찾습니다.

간단해 보여도 정확하게 짜기는 의외로 까다롭습니다. 구간의 끝을 포함하는지, 가운데를 어느 쪽으로 반올림하는지, 찾는 값이 없을 때 어떻게 멈추는지에서 실수가 잦습니다. 가운데를 $(lo + hi)/2$로 계산하면 아주 큰 목록에서 문제가 생깁니다. 컴퓨터의 정수⁠(integer)⁠ 칸에는 담을 수 있는 최댓값이 있습니다(자바의 int는 $2^{31} - 1$, 약 21억). 목록이 $2^{30}$(약 10.7억) 칸을 넘으면 lo + hi가 이 값을 넘을 수 있고, 그러면 엉뚱한 음수가 되어 버립니다. $lo + (hi - lo)/2$로 계산하면 이 문제가 없습니다. 이 오류가 자바 표준 라이브러리에 9년 가까이 숨어 있다가 2006년에야 널리 알려진 일도 있습니다.

이어지는 곳. 같은 생각을 연속함수에 쓰면 중간값 정리⁠(intermediate value theorem)⁠에 기댄 이분법⁠(bisection method)⁠이 됩니다. 부호가 바뀌는 구간을 반씩 잘라 근을 찾는 것으로, 한 번에 한 비트씩 정확해집니다. 뉴턴 방법⁠(Newton's method)⁠은 접선⁠(tangent line)⁠을 써서, 근에서 기울기⁠(slope)⁠가 0이 아니면 근에 충분히 가까워진 뒤로 맞는 자릿수를 매번 두 배쯤으로 늘립니다. 문제를 반으로 줄여 한쪽만 푸는 이진 탐색은 분할 정복⁠(divide and conquer)⁠의 가장 단순한 경우입니다. 이 생각을 자료 구조로 굳힌 것이 이진 탐색 트리⁠(tree)⁠로, 각 점의 왼쪽 가지에는 그보다 작은 값만, 오른쪽 가지에는 큰 값만 두어 뿌리에서부터 이진 탐색하듯 내려가며 찾습니다. 다만 트리가 한쪽으로 기울면 목록과 다를 바 없어지므로, 균형을 유지해야 $O(\log n)$이 보장됩니다. 이진 탐색을 제대로 짰다는 것을 모든 배열과 모든 값에 대해 한꺼번에 보이려면, 'lo 왼쪽은 모두 t보다 작고 hi부터는 모두 t 이상'이라는 조건이 반복마다 유지되고 남은 칸의 수 hi − lo가 매번 줄어든다는 것을 증명합니다. 이 증명과, lo := mid로 쓰면 왜 영원히 도는지는 호어 논리⁠(Hoare logic)⁠에서 한 줄씩 따라가 볼 수 있습니다.