이진 검색

선형 시간 알고리즘보다 더 나은 방법은 없을까? 이름과 전화번호가 적힌 리스트나 명함 다발이 많이 있다고 가정해 보자. 이름이 순서 없이 섞여 있는 상태에서 '김철수'의 전화번호를 찾으려 한다면, 그 이름을 찾을 때까지 리스트를 전부 확인해야 할 것이고, 아예 그 이름을 찾지 못할 수도 있다. 하지만 이름이 한글순으로 되어 있다면 더 쉽게 찾을 수 있다.

 종이로 된 옛날 전화번호부에서 이름을 찾는 방법을 생각해 보자. 보통은 전화번호부 중간쯤부터 보기 시작한다. 만일  찾는 이름이 중간 페이지에 있는 이름보다 알파벳순으로 앞에 있으면 책의 뒤쪽 절반은 완전히 무시하고 앞쪽 절반의 중간(전체의 1/4 지점)을 펼쳐 본다. 그렇지 않으면 책의 앞쪽 절반은 무시하고 뒤쪽 절반의 중간(전체의 3/4)을 확인한다. 이름이 한글순으로 나열되어 있으므로, 다음 단계에 어느 쪽 절반을 찾아야 할지 알 수 있다. 결국 우리는 그 이름이 있는 지점에 도달하거나 목록에 이름이 없음을 확실히 알게 된다.

 이 검색 알고리즘을 이진 검색이라고 한다. 각 확인 또는 비교 단계를 거치면서 항목들이 두 그룹으로 나뉘고, 그 중 한쪽 그룹은 다음 고려 대상에서 제외될 수 있기 때문이다. 이진 검색은 분할 정복이라는 일반적인 전략의 한 가지 예다. 그 속도는 얼마나 빠를까? 각 단계마다 남아 있는 항목의 절반이 제외되므로, 단계의 수는 전체 항목의 크기를 2로 계속 나눠 항목 크기가 1에 도달하게 되는 횟수에 해당한다.

 이름 1024개로 시작한다고 가정해 보자. 이 수는 수월한 계산을 위해 선택된 값이다. 한 번 비교하면 절반인 512개를 검색 대상에서 제외할 수 있다. 한 번 더 비교하면 256개, 이어서 단계별로 128, 64, 32, 16, 8, 4, 2 마지막으로 1이 된다. 세어보면 10번의 비교가 일어났다. 여기서 2¹⁰이 1024라는 것은 결코 우연이 아니다. 여기서 비교 횟수는 2를 거듭제곱했을 때 전체 항목의 수가 되도록 하는 지수다. 각 단계 항목의 개수를 역순으로 1부터 2,4 ⋯ 1024까지 따라가 보면 매번 2를 곱하고 있음을 알 수 있다.

 학교에서 배운 로그를 기억한다면(기억하는 사람이 많지는 않을 것이다. 여기서 로그를 볼 것이라고 누가 생각이나 했겠는가?), 어떤 수의 로그는 그 수에 도달하기 위해 밑수(여기서는 2)에 붙는 지수라는 것을 아마 기억할 것이다. 따라서 밑수 2에 대한 1024의 로그(log₂1024)이 된다. 2¹⁰이 1024이기 때문이다. 알고리즘 맥락에 맞춰 이야기하자면 로그는 어떤 수를 2로 나눠서 1에 도달하기까지의 횟수다. 이 책에서 로그는 항상 밑수 2인 로그를 의미한다. 정밀도나 소수까지는 고려할 필요가 없다. 어림값과 정수값만 보아도 충분한데, 많이 단순화한 것이다.

 이진 검색에서 중요한 점은 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가한다는 것이다. 알파벳순으로 정렬된 이름 1000개가 있을 때, 특정 이름을 찾으려면 이름 10개를 확인해야 한다. 이름 2000개가 있다면 이름 11개만 확인하면 된다. 왜냐하면 첫 번째로 이름을 확인하는 즉시 2000개 중 1000개가 검색 대상에서 제외되어, 두 번째 검사부터는 1000개만 가지고 확인하면 되기 때문이다. 즉 이름은 1000개 늘었지만 검사 횟수는 1번 늘어났을 뿐이다. 이름이 100만 개 있다고 하자. 100만은 1000의 1000배이므로 검사를 10번 하면 1000개까지 검색 대상을 줄일 수 있고, 다시 검사를 10번하면 검색 대상이 한 개가 되므로 총 20번의 검사가 일어난다. 100만은 10⁶으로 2²⁰에 가깝기 때문에 100만의 로그는 약 20이 된다.

 이상에서, 이름이 10억 개 담긴 전화번호부(거의 전 세계 전화번호부가 되겠다)에서 이름을 찾으려 한다면 10억은 약 2³⁰이기 때문에 30번만 이름을 비교하면 된다는 것을 알 수 있다. 이러한 이유로 작업의 양이 데이터의 양에 비해 천천히 증가한다고 하는 것이다. 데이터의 양이 1000배 많아지더라도 10번의 단계만 더 필요하다

 실생활에서 이런 이진 나눗셈을 어렵지 않게 찾아볼 수 있는데, 스포츠 경기에 자주 사용되는 단계별 토너먼트 같느 상황이 이에 해당한다. 토너먼트는 많은 수의 경쟁자들로 시작한다. 예를 들면 128명의 선수로 경기가 시작한다. 각 회전에서 경쟁자들이 절반씩 탈락해서 결승에서는 선수 두 명만 남고, 이 중에서 단독 승자가 나온다. 128은 2의 거듭제곱(2⁷)이라서 7번의 회전이 있다. 전 세계인이 모여서 하는 단계별 토너먼트를 상상해 볼 수도 있을 것이다. 70억 명의 참가자가 있더라도 승자를 결정하는 데는 단지 33번의 회전이 필요하다