2.4.1 깜짝 퀴즈
이진 검색의 효율성을 완벽히 이해시켜 주는 깜짝 퀴즈를 준비했다. 정답을 가리고 제대로 이해했는지 확인하자.
문제: 원소가 100개인 정렬된 배열에서 이진 검색은 7단계가 걸렸다. 원소가 200개인 정렬된 배열에서 이진 검색은 몇 단계가 걸릴까?
정답: 8단계
직관적으로 14단계라고 답하는 경우가 종종 있는데 틀렸다. 이진 검색의 묘미는 검사할 때마다 남은 원소의 반을 제거하는 데 있다. 그러니 데이터 크기를 두 배로 늘릴 때마다 1단계만 늘어난다. 두 배로 늘린 데이터는 첫 번째 검사에서 결국 모두 제거된다!
이진 검색이라는 새 도구가 생겼으니 정렬된 배열에의 삽입도 더 빨라질 수 있다는 점에 주목해 볼만하다. 삽입하려면 먼저 검색이 필요한데 이제 그 검색을 선형 검색에서 이진 검색으로 업그레이드할 수 있다. 물론 일반 배열에의 삽입에는 검색이 전혀 필요 없으니 정렬된 배열에의 삽입이 여전히 일반 배열보다 느리다.