Answers · Making it fast enough
How does binary search find something in a sorted list so fast?
In shortBinary search is fast because each comparison halves the remaining sorted range, so a thousand items need about ten probes and a million need about twenty, rather than one probe per item.
Binary search is fast because every comparison halves the remaining interval, so the number of probes is the number of times the list can be halved: about for items. It is not fast because it skips elements in some clever way. The skipping is a consequence of the count, not the cause.
Take a sorted list of the numbers 1 to 1000 and look for 732. The first middle is 500. Since 732 is larger, every number from 1 to 500 is too small, so the remaining interval is 501 to 1000, size 500. The next middle is 750. Since 732 is smaller, keep 501 to 750, size 250. The middles then fall at 625, 688, 719, 735, 727, 731, and 733, leaving intervals of sizes 125, 62, 31, 15, 7, 3, and 1, and the last comparison finds 732. That is ten comparisons, not a thousand.
The count, not the skipping
The natural guess is that binary search is quick because each step throws away a large block of entries, as if the speed came from the size of the jump. That cannot be the explanation by itself. A method that threw away 999 entries in one leap and then had to do that a thousand times would still be a thousand steps. What changes the order of growth is that the interval is halved at every probe, so the number of probes is the depth of halving, not the number of entries discarded. For 1000 items the depth is 10 because ; for a million it is 20 because ; for a thousand million it is 30 because . A single probe may discard half a million entries, but the reason the whole search is short is that there are only about twenty such probes.
| items | probes in the worst case | one-by-one steps |
|---|---|---|
| 1000 | 10 | 1000 |
| 1,000,000 | 20 | 1,000,000 |
| 1,000,000,000 | 30 | 1,000,000,000 |
The discarded half is not guessed away. The comparison against the middle uses the sorted order to prove something about every entry in that half. If the target is greater than the middle entry, then every entry at or before the middle is at most the middle entry, so every one of them is less than the target and none can be the target. The same argument in reverse removes the upper half when the target is smaller. One comparison therefore eliminates half the list with certainty. That is why sortedness is not a detail: without it, a comparison against the middle says nothing about the entries on either side, and no half can be discarded.
Where the halving stops paying
The logarithmic count assumes two things: the list is sorted, and the middle of the current interval can be reached in constant time. An array gives the second. A linked list does not. To halve a linked list you must walk to its middle, which costs work proportional to the interval, and the total becomes linear rather than logarithmic. If the list is unsorted, the first comparison proves nothing about the other entries, so the method is simply invalid. Duplicates are a smaller qualification: ordinary binary search finds some occurrence of the target, not necessarily the first one, unless the comparison is changed to keep searching left after a hit. And if comparisons are expensive, the depth is still logarithmic but the constant factor is the cost of a comparison.
The number of levels grows so slowly that it is almost never the thing to optimise. Going from a thousand items to a million adds ten probes; going from a million to a thousand million adds ten more. The work per probe is one comparison, so the total is that comparison repeated about times. The speed is a count of halvings, not a trick of jumping.
Worth keeping
- Halving a range of n items takes about log base two of n steps, so a million items need about twenty halvings and a thousand million need about thirty.
- A binary search does not skip elements by luck; one comparison against the middle proves that an entire half cannot contain the target.
- Binary search needs a sorted list and fast access to the middle; without either, halving stops being cheap.
Where this goes next
This question is one step of Answers Built From Smaller Answers, a course that works through its subject from the beginning. The page that teaches this part of it is Splitting the Work in Half, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- What's the difference between memoized recursion and filling a DP table bottom-up?Memoised recursion keeps the calls and only solves states it reaches; a bottom-up table removes the calls, fills every entry in a dependency-safe order, and is usually faster when most entries are needed.
- Why is merge sort O(n log n) when it keeps splitting the array in half?Splitting in half gives about twenty levels for a million items, and merging at every level still touches all million items, so the total is twenty million rather than a million times a million.
- When is picking the locally best option actually guaranteed to give the best overall answer?Only when a proof shows that some best overall answer can contain the locally best first choice, and the same holds for every later step; otherwise one counterexample can break it.
- What is memoization and why does caching recursive results make it so much faster?Memoisation stores each answer once and reuses it, so a recursion that repeats the same subproblems stops redoing work and becomes a table lookup instead.
- Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
- Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.