데이터 개수를 n, 비교 횟수를 k라 할 때 공식은 다음과 같습니다.

우리가 구하고자 하는 값은 k입니다. k는 지수이므로 적당히 정리하여 로그를 취하면 됩니다.

그래프로 표현하면 그림 15-4와 같습니다(성능 비교를 위해 선형 탐색은 점선으로 표시하였습니다).

그림 15-4 선형 탐색 알고리즘 vs. 이진 탐색 알고리즘

데이터 개수가 늘어날수록 이진 탐색의 비교 횟수가 선형 탐색에 비해 현저하게 줄어드는 것을 알 수 있습니다. 이처럼 결과는 같아도 알고리즘에 따라 성능은 크게 달라집니다.