3알고리즘 분석

 

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 탐색 알고리즘입니다. 예를 들어 자료가 천 개 있을 때 원하는 자료를 찾는다고 생각해 보겠습니다. 순차 탐색은 최악의 경우에 자료 천 개와 모두 비교해야 하지만, 이분 탐색은 최악의 경우에도 자료 열 개와 비교하면 탐색을 마칠 수 있습니다(log₂ 1,000≅9.966).

 

그림 12-5 이분 탐색으로 탐색 범위를 1까지 좁혀 가는 과정

 

이분 탐색의 계산 복잡도는 O(logn)으로, 순차 탐색의 계산 복잡도인 O(n)보다 훨씬 더 효율적입니다.

대한민국 전 국민 오천만 명 중에서 주민등록번호로 한 명을 찾는다고 해 볼까요? 순차 탐색으로는 최악의 경우 주민등록번호가 같은지 오천만 번 비교해야 하지만(찾는 사람이 자료의 맨 마지막에 있을 때), 이분 탐색으로는 최악의 경우라도 26명의 주민등록번호와 같은지 혹은 큰지를 비교하면 원하는 사람을 찾을 수 있습니다(log₂ 50,000,000≅25.575).

물론 이분 탐색을 가능하게 하려면 자료를 미리 정렬해 둬야 해서 번거로울 수 있습니다. 하지만 필요한 값을 여러 번 찾아야 한다면 시간이 조금 걸리더라도 자료를 한 번 정렬한 다음에 이분 탐색을 계속 이용하는 방법이 훨씬 효율적입니다.