작은 크기의 정렬된 배열이라면 이진 검색 알고리즘이 선형 검색 알고리즘보다 크게 나은 점이 없다. 하지만 배열이 더 커지면 어떨지 보자.

100개의 값을 갖는 배열에서 각 검색에 필요한 최대 단계 수는 다음과 같다.

선형 검색에서는 찾고 있는 값이 마지막 셀에 있거나 마지막 셀의 값보다 크면 모든 원소를 조사해야 한다. 원소가 100개인 배열이면 100단계가 걸린다.

하지만 이진 검색을 쓰면 추측할 때마다 검색해야 할 셀 중 절반을 제거할 수 있다. 첫 번째 추측에서 셀을 50개나 제거해버린다.

다른 관점에서 보면 어떤 패턴이 보인다.

배열의 크기가 3일 때 이진 검색에 필요한 최대 단계 수는 2다.

배열의 크기를 두 배로 늘리면(단순한 계산을 위해 한 칸을 더 추가해서 홀수로 유지하면) 크기가 7이 되고, 이진 검색에 필요한 최대 단계 수는 3이 된다.

배열의 크기를 두 배(그리고 한 칸 더 추가)로 늘리면 크기가 15가 되고 이진 검색에 필요한 최대 단계 수는 4가 된다.

정렬된 배열의 크기를 두 배로 늘릴 때마다 이진 검색에 필요한 단계 수가 1씩 증가하는 패턴이 보인다. 값을 확인할 때마다 검색할 원소의 절반을 제거하니 이치에 맞다.