Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?
- A. 3.00
- B. 3.46
- C. 2.81
- D. 3.33
Answer: A. 3.00
Explanation: For 11 items, levels are 1, 2, 4, 4 (Total 11). \nDepths: 1 node at 1, 2 nodes at 2, 4 nodes at 3, 4 nodes at 4.\nTotal comparisons = $1 \times 1 + 2 \times 2 + 4 \times 3 + 4 \times 4 = 1 + 4 + 12 + 16 = 33$.\nAverage = $33 / 11 = 3.00$.