오름차순으로 정렬된 서로 다른 1,000개의 값에서 이진 탐색으로 값을 찾는다. 1회의 비교로 '일치·더 작다·더 크다'를 알 수 있다고 하면, 찾는 경우와 찾지 못하는 경우를 모두 포함하여 비교 횟수는 최대 몇 회인가?

정답: A. 10회

1회의 비교로 찾는 범위가 거의 절반이 되며, 2¹⁰ = 1024 ≥ 1000이므로 최대 10회면 범위가 없어집니다(⌊log₂ 1000⌋ + 1 = 10). 시간 복잡도는 O(log n)이며, 100만 개라도 최대 20회면 됩니다. 32회는 √1000 ≈ 31.6에 해당하는 값이고, 500회는 선형 탐색의 평균(약 n/2)에 가까운 값입니다. 다만 이진 탐색을 사용하려면 데이터가 정렬되어 있어야 하며, 정렬에 드는 O(n log n)의 수고도 고려해야 합니다.