Data Structures and Algorithms
A binary search looks for 38 in the ascending array a[0] to a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60. The search range starts with lo = 0 and hi = 9, and the middle position is (lo + hi) ÷ 2 rounded down. Which lists, in order, the elements compared with 38?
- A23, 38
- B31, 52, 45, 38
- C23, 45, 31, 38
Show answer and explanation
Answer: C. 23, 45, 31, 38
First, (0 + 9) ÷ 2 = 4, so 38 is compared with a[4] = 23; 38 is larger, so lo = 5. Next, (5 + 9) ÷ 2 = 7, so it is compared with a[7] = 45; 38 is smaller, so hi = 6. Then (5 + 6) ÷ 2 = 5 gives a[5] = 31, so lo = 6, and finally a[6] = 38 matches. That is 4 comparisons, the maximum for 10 elements, ⌊log₂ 10⌋ + 1 = 4. The order 31, 52, 45, 38 results from rounding the middle up, which is not the rule given in the question.
- A. After comparing with 23, the next comparison is with a[7] = 45, the middle of the remaining range a[5] to a[9].
- B. This is the order when the middle is rounded up, which differs from the rule in the question.
- C. Correct. It compares a[4], a[7], a[5] and a[6] in turn and finds the value on the fourth comparison.