Binary Search
Easy+50 XPFind a target in a sorted array by repeatedly halving the search space.
Where it breaks
Binary search only works on a SORTED array.See what happens when you don't.
No visualization loaded.
Watch
—
Press Run to begin.
Binary search is the payoff for sorting. Because the array is in order, you can peek at the MIDDLE box and instantly throw away half the array: if the middle is too small, your target must be to the right, so the whole left half is gone — and vice versa. Repeat on what's left, halving every time, until you land on it. It's the classic 'higher or lower?' guessing game played on a sorted row of boxes.
▸What are 'lo', 'hi', and 'mid' — they show up in the animation?
They're just three bookmarks. 'lo' marks the leftmost box still in play, 'hi' marks the rightmost, and 'mid' is the box halfway between them that we check this round. After each check we move lo or hi inward to shrink the live range. When lo passes hi, there's nothing left to check — the target isn't there.
▸Why does checking the middle let me throw away HALF?
Only because the array is sorted. If the middle box is smaller than your target, then every box to its LEFT is also smaller (sorted = never goes down), so none of them can be your target — toss them all at once. If the middle is bigger, the right half is gone instead. One comparison eliminates half the remaining boxes. That's the whole trick.
▸What's 'O(log n)' and why is it so much better than O(n)?
O(n) (linear search) means the work grows with the number of boxes. O(log n) means it grows with the number of TIMES you can halve them. 1000 boxes? Halving gets you to 1 in about 10 steps. A MILLION boxes? Only about 20 steps. Linear search might do a million checks; binary search does ~20. That gap is why sorting first is often worth it — and it's the single biggest speed idea in this whole course.
▸What happens if the target isn't in the array?
You keep halving until the live range is empty — lo crosses past hi with no box left to check. At that point you can be CERTAIN it's absent, because every box you discarded was provably on the wrong side. So binary search answers 'not found' just as fast as it answers 'found': about log n steps either way.
▸Why does it HAVE to be sorted? What if I forget?
The entire 'throw away half' move assumes smaller values are on the left. On unsorted data that assumption is false, so binary search can discard the half that actually holds your target and confidently report 'not found.' Try the 'Where it breaks' button below to watch it happen — it's the best way to feel why sorting isn't optional here.
How the work grows
O(log n) is excellent — barely grows. Each step throws away half the boxes, so the work grows with how many times you can halve n — about 20 steps for a million boxes. Barely climbs as data grows.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.