What's the fastest way to find one name in a giant sorted list?
Did this make sense?
Your thumbs help us make it clearer.
Thanks! That helps us make it clearer. 💜
See it another way
Unplugged: The show. Part 10: Binary search - divide and conquer
A live card hunt shows how each middle peek erases half a sorted row—even when the row grows to a million places.
Requires internet. You’re leaving Clickory in a new tab; YouTube may show ads or recommendations.
Keep going
What else makes you wonder?
How can a search engine find one word across the whole internet in a blink?
The internet is not one giant alphabetized list. What could a search engine build ahead of time so it already knows which pages contain each word?
Could a searcher make a smarter first jump than the exact middle?
If the cards rise by even steps and you want #88, the number itself hints where to land. What breaks when the gaps between cards are lumpy?
How do you keep a giant list sorted while new names keep arriving?
Sliding a million cards over for every new name would be awful. Could you divide the list into smaller ordered shelves and rearrange only one shelf?
After you watchWhat's the fastest way to find one name in a giant sorted list?
The short answer
A reliably fast way to comparison-search an already sorted list is to read the middle item, discard the half that cannot contain the target, and repeat. This is binary search. Each comparison can erase a large part of the remaining work, while reading from the start may require many more checks. Other structures, such as prebuilt indexes, make different tradeoffs.
Try this next
- What if the list gets way bigger? Start with 200 sorted names. Predict whether the halver needs twice as many peeks or only one more, then halve the possible places on paper: 200 → 100 → 50 → 25… How many cuts until one name remains?
- What if the name you want is near the front? Imagine hunting for Ava at place 2 instead of Ravi at place 88 — the creeper would win for once. When is one-by-one actually the faster choice?
- What if the list isn't sorted? Picture the names shuffled into a random pile. Try to throw away every name through the middle one — why does the halver's trick fall apart the instant the order is gone?
The whole story
How it works
Because the names run from A to Z, you can read the middle name and compare it with the one you want. If your target belongs later in the alphabet, the entire earlier half can go; if it belongs earlier, the later half can go. Then you read the middle of the names still possible and repeat. The search space keeps being cut roughly in half until only the target remains. Reading every name from the start instead (linear search) is simple but can be much slower.
What people get wrong
It feels like a bigger list must mean lots more searching, so people assume you have to scan through most of the names to be safe. With a sorted list that is wrong. Doubling the list does double the work for the one-by-one searcher, but it adds only ONE extra peek for the halving searcher, because that one extra cut is enough to discard the whole extra half.
The catch
The halving trick is not free. It only works if the list is already sorted; on a jumbled pile, throwing away 'the left half' tells you nothing, so you are stuck checking one by one. And sorting a list takes work up front, so for a single quick lookup it may not be worth it. The win comes when you search the same list again and again: you maintain the order as the list changes, then reuse it for many quick searches.
Questions kids ask
Why does the middle-jumping search find things so much faster?
Each peek at the middle lets it throw away half of whatever is left, so the pile of possible cards shrinks very quickly instead of being checked one at a time.
Why does the list have to be sorted first?
The trick relies on order: if a card is too big, everything to its right must be too big as well, so a whole half can be safely tossed. In a jumbled list that promise breaks, and you have no way to know which half to discard.
How many peeks does it take for a really huge list?
Each peek roughly halves the list, so a million cards take about 20 peeks and a billion take only about 30. That is why searching contacts or a giant index feels instant even when the list is enormous.
When is checking one card at a time actually better?
When the list is short, when it isn't sorted, or when you only search it once. Sorting a list takes effort, so if you aren't going to search it many times, plain one-by-one searching can be the simpler, faster choice.
Talk about it
- Ask them: the halver throws away half the names on its very first peek, before it has even seen most of them. How can it be so sure none of those names is Ravi?
- Ask: a phone finds a contact among thousands instantly. What has to be true about how those contacts are stored for that to work?
For grown-ups
This contrasts binary search with linear search. Linear search is O(n): its cost grows in step with the list. Binary search is O(log₂n): each comparison halves the remaining search space, so even very large lists need surprisingly few comparisons. The precondition is that the data is sorted, and maintaining sorted order has its own cost (a one-time comparison sort is O(n·log n)), which is exactly why binary search pays off for data that is searched far more often than it changes.