유일 키를 갖는 자료 1,000개가 키에 의해 오름차순으로 정렬되어 있… | [방송통신기사 필기] 19년 1회차 기출문제 상세 페이지

정렬된 1,000개 자료를 이진탐색할 때 최대 비교 횟수는 10회이다.
한 번 비교할 때마다 탐색 범위가 절반으로 줄어 최대 횟수는 $\lfloor \log_{2} 1000 \rfloor + 1$ 이다.
$2^{9} = 512 \lt 1000 \lt 1024 = 2^{10}$ 이므로 $9 + 1 = 10$ 회이다.
5회는 $2^{5} = 32$ 개까지만 탐색할 수 있어 1,000개에 부족하다.
500회는 매번 절반으로 줄이는 이진탐색의 비교 횟수보다 훨씬 크다.
1,000회는 자료를 처음부터 하나씩 비교하는 순차탐색의 최악 횟수이다.