Computer science · Grades 9–12
Worst-case comparisons in a perfect binary search
The array is sorted and balanced median choices are used. Count inspected elements, including the last one.
Method and conditions
The array is sorted and balanced median choices are used. Count inspected elements, including the last one.
Maximum comparisons = log₂(N+1) when N=2ᵏ−1
Worked examples
A sorted array has 2047 entries. Binary search always inspects a middle entry. What is the largest number of inspected entries for a successful search? Round the final result to 4 decimal places if needed.
A perfect binary decision tree with 2047 entries has 11 levels. A deepest successful search inspects one entry per level.
11
A sorted array has 15 entries. Binary search always inspects a middle entry. What is the largest number of inspected entries for a successful search? Round the final result to 4 decimal places if needed.
A perfect binary decision tree with 15 entries has 4 levels. A deepest successful search inspects one entry per level.
4
Try it
A sorted array has 63 entries. Binary search always inspects a middle entry. What is the largest number of inspected entries for a successful search? Round the final result to 4 decimal places if needed.
A sorted array has 16383 entries. Binary search always inspects a middle entry. What is the largest number of inspected entries for a successful search? Round the final result to 4 decimal places if needed.
Check your work
Answers and marking notes
- 6
A perfect binary decision tree with 63 entries has 6 levels. A deepest successful search inspects one entry per level.
- 14
A perfect binary decision tree with 16383 entries has 14 levels. A deepest successful search inspects one entry per level.
AI-assisted preview; independent educational review required. Level labels describe prerequisites, not accreditation or official curriculum alignment.