What's the fastest way to find one name in a giant sorted list?
After you watchWhat's the fastest way to find one name in a giant sorted list?
The short answer
The fastest way to find one name in a giant sorted list is to peek at the middle, then throw away the whole half that can't contain it, and repeat. This is called binary search, and it finds a name among 100 in about 7 peeks, among a million in about 20, because every peek deletes half the list at once.
Try this next
- What if the list gets way bigger? Tap 'Double the list' a few times and watch the halver's peek count crawl up by just one each time, while the creeper's doubles.
- What if the card you want is near the front? Imagine hunting for card #2 instead of #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 cards shuffled into a random pile. Try to 'throw away the left half' — why does the halver's trick fall apart the instant the order is gone?
The whole story
How it works
Because the list is in order, you can jump straight to the middle card and compare. If the name you want comes after it, the entire first half is too small to hold it, so you delete that half for good and look only at the second half. You jump to the new middle and repeat. Each peek cuts the leftover list in half, so the number of cards you might still have to check goes 100, 50, 25, 12, 6, 3, 1, landing in roughly seven peeks. Checking every card from the start instead (called linear search) is simple but slow, because you might peek at almost every card.
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 isn't worth it. The win comes when you search the same list again and again, like a phone scanning its contacts, where you sort once and search instantly forever after.
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 from 100 to 50 to 25 and so on. It reaches one card in about seven peeks instead of checking them 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 cards on its very first peek, before it has even seen most of them. How can it be so sure none of those cards is the one we want?
- 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 a list of n needs only about log₂(n) comparisons (100 → ~7, a million → ~20, a billion → ~30). 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.
Keep going
What else makes you wonder?
- A phone book is sorted by name — but what clever trick lets a search engine find a word across the whole internet in a blink?
- If halving is so fast, is there a way to jump even closer than the exact middle on the very first peek?
- How do you keep a giant list sorted when new names keep getting added all the time?