이러한 증가 패턴은 대단히 효율적이다. 데이터를 두 배로 늘릴 때마다 이진 검색 알고리즘에서는 최대 한 단계만 더 추가된다.

선형 검색과 대조해 보자. 원소가 3개 있으면 최대 3단계가 필요하다. 원소가 7개 있으면 최대 7단계가 필요하다. 100개면 최대 100단계가 필요하다. 선형 검색에서는 원소 수만큼의 단계가 필요하다. 배열의 원소 수를 두 배로 늘릴 때마다 검색에 필요한 단계 수도 두 배로 늘어난다. 이진 검색에서는 배열의 원소 수를 두 배로 늘릴 때마다 한 단계만 늘어난다.

더 큰 배열에서는 어떤 양상이 나타날까? 원소가 10,000개인 배열에서 선형 검색은 최대 10,000단계가 걸리지만, 이진 검색은 최대 13단계면 충분하다. 크기가 1,000,000개인 배열에서 선형 검색은 최대 1,000,000단계가 걸리지만, 이진 검색은 최대 20단계면 된다.

선형 검색과 이진 검색 간 이러한 성능 차이를 그래프로 표현했다.

▲ 그림 2-19

이와 같은 그래프를 앞으로 많이 해석해야 하니 무엇을 뜻하는지 잠시 이해하는 시간을 갖자. x축은 배열 내 원소 수를 나타낸다. 즉 왼쪽에서 오른쪽으로 갈수록 더 많은 데이터를 처리한다.

Y축은 알고리즘에 걸리는 단계 수를 나타낸다. 그래프 위쪽으로 올라갈수록 단계가 더 많아진다.