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?
Answer: A. 3.00 — 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…
- A.
3.00
- B.
3.46
- C.
2.81
- D.
3.33
Attempted by 321 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2