1부 하드웨어 020. 10억 개 전화번호에서 이름 찾기: 이진 검색
검색 알고리즘 '이진 검색(binary search)'이라고 한다. 각 확인 또는 비교 단계를 거치면서 항목들이 두 그룹으로 나뉘고, 그 중 한쪽 그룹은 다음 고려 대상에서 제외될 수 있기 때문이다.
이진 검색은 분할 정복(divide and con-quer)이라는 일반적인 전략의 한 가지 예다. 각 단계마다 남아 있는 항목의 절반이 제외되므로, 단계의 수는 전체 항목의 크기를 2로 계속 나눠 항목 크기가 1에 도달하게 되는 횟수에 해당한다.
이진 검색에서 중요한 점은 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가한다는 것이다.
예를 들어 이름이 10억 개 담긴 전화번호부에서 이름을 찾으려 한다면 10억은 약 2의 30제곱이기 때문에 30번만 이름을 비교하면 된다는 것을 알 수 있다.
이러한 이유로 작업의 양이 데이터의 양에 비해 천천히 증가한다고 하는 것이다. 데이터의 양이 1,000배 많아지더라도 10번의 단계만 더 필요하다.
실생활에서 이런 이진 나눗셈을 어렵지 않게 찾아볼 수 있는데, 스포츠 경기에 자주 사용되는 단계별 토너먼트 같은 상황이 이에 해당한다.
70억 명의 참가자가 있더라도 승자를 결정하는 데는 단지 33번의 회전이 필요하다.
