Search by Eliminating Half the Possibilities
What This Concept Is
Binary search is a way to find something in a sorted collection by repeatedly checking the middle and throwing away the half that cannot contain the answer. Instead of asking "Is it here? Is it here? Is it here?" one item at a time, it asks, "Which half is still possible?"
Why It Matters Here
This is the cleanest first example of algorithmic leverage. The code is not magical or complicated. The win comes from a better question: if the data is sorted, you can eliminate huge chunks of work at once.
Concrete Example
Imagine a sorted list of numbers:
[3, 8, 12, 17, 21, 29, 34, 42]
If you want 29, start in the middle with 17.
17is too small, so the left half is impossible.- Search only
[21, 29, 34, 42]. - Middle is
29. - Done in two checks.
Simple search might need to inspect six items before landing on 29. Binary search succeeds quickly because each check eliminates half the remaining possibilities.
Common Confusion / Misconception
Binary search is not "any search that feels fast." It only works when the collection is already ordered in a way that lets "too low" and "too high" eliminate whole regions. If the data is unsorted, cutting the collection in half tells you nothing useful.
How To Use It
Use binary search when all of these are true:
- the data is sorted by the thing you are searching on
- you can inspect a middle position
- each comparison lets you discard half the remaining space
If one of those conditions breaks, switch strategies. The algorithm is not the point by itself; the preconditions are part of the algorithm.
Check Yourself
- Why does sorted order matter for binary search?
- If you inspect the midpoint and the value is too high, what exactly becomes impossible?
- What happens if you try binary search on a shuffled list?
Mini Drill or Application
Trace binary search on this list and record the midpoint at each step:
[2, 5, 9, 12, 16, 21, 27, 31, 38, 44, 50, 57, 63, 70, 88, 91]
Search once for 31 and once for 26. For each search, write:
- midpoint value checked
- whether you moved left or right
- which range remained possible
If you finish quickly, explain in one sentence why the failed search still ends with certainty.