오름차순으로 늘어선 배열 a[0]~a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60에서 이진 탐색으로 38을 찾는다. 찾는 범위를 하한 lo = 0, 상한 hi = 9에서 시작하고, 가운데 위치를 (lo + hi) ÷ 2의 버림으로 한다. 38과 비교되는 원소의 값을 차례로 나열한 것은?

정답: C. 23, 45, 31, 38

처음에는 (0 + 9) ÷ 2 = 4로 a[4] = 23과 비교하고, 38이 더 크므로 lo = 5로 합니다. 다음은 (5 + 9) ÷ 2 = 7로 a[7] = 45와 비교하고, 38이 더 작으므로 hi = 6으로 합니다. 다음은 (5 + 6) ÷ 2 = 5로 a[5] = 31과 비교하여 lo = 6으로 하고, 마지막으로 a[6] = 38에서 일치합니다. 비교는 4회로, 원소 수 10일 때의 최대 횟수 ⌊log₂ 10⌋ + 1 = 4에 해당합니다. 31, 52, 45, 38은 가운데를 올림으로 한 경우의 순서로, 문제에서 정한 방식과 다릅니다.