Clickory

What's the fastest way to find one name in a giant sorted list?

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?

ages 8–11How does a computer remember things even after you turn it off? Open ages 8–11How does a phone shrink a huge photo small enough to send in a flash? Open ages 8–11How does a song fly through the air into your radio? Open
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. In the story, it finds Ravi at place 88 after reading just 3 names and guarantees any name among 100 in at most 7 comparisons; a million takes at most 20. 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 you want Ravi and the middle says Mia, every name from A through Mia is too early in the alphabet, so that whole half can go. Then you read the middle of the names still possible and repeat. The possibilities shrink 100, 50, 25, 12, 6, 3, 1. Six halving cuts can leave one possible name, and one final comparison checks it, so even the hardest target needs no more than seven peeks. 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 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 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 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.