2.6Binary search and selection
The idea
Binary search finds a key in a sorted array by halving the range each time; it needs random access.
Think of it like this: Looking for a name in a phone book: open in the middle, then go to the correct half.
Why it exists
It is the model for logarithmic time, and the min/max comparison counts are classic formulas.
How it works
- Compare the key with the middle element.
- If equal: done. If smaller: search the left half. If larger: search the right half.
- Worst case ⌊log₂ n⌋ + 1 probes.
- Min of n items: n − 1 comparisons; min and max together: ⌈3n/2⌉ − 2.
Worked example: n = 100
Binary search needs at most 7 probes; finding min and max together takes ⌈150⌉ − 2 = 148 comparisons.
Now play with it
- →Search for a value that is missing and count the probes.
- →Use the calculator for different n.
- lo = 0, hi = 9, mid = 4: a[mid] = 16 < target: go right (lo = mid + 1)
- lo = 5, hi = 9, mid = 7: a[mid] = 56 > target: go left (hi = mid − 1)
- lo = 5, hi = 6, mid = 5: a[mid] = 23 = target: found
Check yourself
The least number of comparisons needed to find both the minimum and the maximum of 8 distinct numbers is
Exam notes (the dense version)
Binary search on a sorted array takes ⌊log₂ n⌋ + 1 probes in the worst case. It needs random access. Selection (k-th smallest) can be done in expected O(n) with quickselect and worst-case O(n) with median of medians. Finding the minimum takes n − 1 comparisons; finding both min and max takes ⌈3n/2⌉ − 2.
Previous year questions: Sorting & Searching (9)
PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.