Binary Search on Sorted Data
Finding a value in sorted data by halving the range that is still in play at every step, and the reason the method breaks on unsorted data.
What a learner can do afterwards
- Step through a binary search on a sorted list and count the checks
- Say what happens to the range still being searched after each comparison
- Explain why the data must be sorted, and when that sorting cost is worth paying
1 · Read
Binary search hunts sorted data by halving. Compare the target with the middle item, keep the half that can still hold it, and drop the rest. Every round kills about half of what is left.
Hunt 57 in sorted 3, 37, 45, 57, 93 and 120. The middle reads 45, and 57 tops it, so the lower half drops away. The hunt continues in 57, 93 and 120 with far fewer suspects.
The whole trick rests on order. On jumbled data the dropped half might hide the target, so the method breaks. Sort first, then halve.
Sorting costs effort up front, so pay it when many hunts follow. A thousand sorted items need about ten halvings against up to a thousand one-by-one checks.
On sorted data, compare the middle, drop the dead half, and repeat until found or empty.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.