Computer science · Grades 9–12
Worst-case comparisons in a perfect binary search · formula reference
The array is sorted and balanced median choices are used. Count inspected elements, including the last one.
Formula
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 example
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
Prerequisites and checking
Algebra and the topic definitions. Keep units and rounding consistent. State the model conditions before applying the formula.
AI-assisted preview; independent educational review required. Level labels describe prerequisites, not accreditation or official curriculum alignment.