Suppose there are 11 items in sorted order in an array. How many searches are…
2014
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
Attempted by 166 students.
Show answer & explanation
Correct answer: A
For a binary search on n=11 items, we analyze the decision tree structure.
The tree levels have node counts: Level 1 has 1 node, Level 2 has 2 nodes, Level 3 has 4 nodes, and Level 4 has 4 nodes.
Total comparisons = (1×1) + (2×2) + (3×4) + (4×4) = 1 + 4 + 12 + 16 = 33.
Average comparisons = Total / n = 33 / 11 = 3.00.