10억 개 전화번호에서 이름 찾기:이진검색
선형 시간 알고리즘보다 더 나은 방법은 없을까?
종이로 된 옛날 전화번호부를 생각해보자. 만약 찾는 이름이 알파벳순으로 뒤에 있다면 그에 해당하는 알파벳 부분을 넘겨서 확인할 것이다.
이런 검색 알고리즘을 이진 검색(binary search)라고 한다. 각 확인 또는 비교 단계를 거치면서 항목들이 두 그룹으로 나뉘고, 그중 한쪽 그룹은 다음 고려 대상에서 제외될 수 있기 때문이다. 이진 검색은 분할 정복(divide and conquer)의 일반적인 전략의 한 예시이다.
그 속도는 각 단계마다 남아 있는 항목의 절반이 제외되므로, 단계의 수는 전체 항목의 절반이 제외되므로, 단계의 수는 전체 항목의 크기를 2로 계속 나눠 항목 크키가 1에 도달하게 되는 횟수에 해당한다. 이는 수학에서의 로그와 비슷한데(나는 전혀 모르겠지만) 로그도 마찬가지로 어떤 수를 2로 나눠서 1에 도달하기까지의 횟수, 또는 2를 거듭제곱해서 그 수까지 도달하기까지의 횟수다. 밑수 2인 로그와 같다.
이진 검색에서 중요한 점은 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가한다는 것이다. 알파벳순으로 정렬된 이름 1,000개가 있다면 특정 이름을 찾을 때 이름 10개만 확인하면된다. 2,000개 있다면 11개만 확인하면 된다. 왜냐하면 2,000개 중에서 한번 검색하면 1,000개가 검색 대상에서 제외되기 때문이다. 이런식으로밖에 안늘어나기 때문에 100만의 로그는 약 20밖에 되지 않는다. 10억이면? 30번밖에 되지 않는다.
실생활에 쓰이는 예시로는 단계별 토너먼트 상황이 있다. 70억명의 참가자가 있더라도 승자를 결정하는 데는 단지 33번의 회전만 있으면 된다. :o
