1.4이진 탐색 알고리즘의 성능

이진 탐색 알고리즘의 성능은 어떻게 분석해야 할까요? 그림 15-2의 리스트에서 대상 데이터가 5라면 단 한 번의 비교로 찾을 수 있습니다(최선의 경우). 대상 데이터가 1이면 비교 횟수는 늘어날 것입니다(최악의 경우). 이번에도 최악의 경우를 계산합니다.

그림 15-3은 대상 데이터가 1인 경우를 나타냅니다.

그림 15-3 worst case

데이터 개수가 10일 때 비교 횟수는 3입니다. 데이터 개수를 n이라고 일반화하면 비교 횟수는 어떻게 될까요? mid 데이터와 target 데이터를 한 번 비교할 때마다 비교해야 할 데이터 개수는 절반으로 줄어듭니다. 연산을 계속하다 보면 비교해야 할 데이터가 하나 남는데, 이때 마지막으로 한 번만 더 비교하면 최악의 경우에서의 비교 횟수를 구할 수 있습니다.