You're previewing the Bennett demo family. Numbers, schedule, and kids are sample data.Start your own
Loading page…
Search a billion things and the answer comes back before you have let go of the key. The obvious explanation is that the computer looked at a billion things very quickly. It did not. It looked at about thirty.
Type a name into a phone, a website, a shop, and the result arrives instantly. Everyone's explanation is the same: computers are fast, and it checked all of them in no time.
Here is why that cannot be the whole story. Checking a billion things one after another, at the speed a computer really works, takes long enough to notice — and a search that has to touch every item gets twice as slow every time the list doubles. Yet these searches barely slow down at all as the list grows. Something else is going on.
The real answer is almost insulting in how ordinary it is. The computer does not look at everything. It looks at hardly any of it. And the method it uses is one you have already used, probably at a party, definitely in a guessing game.
Suppose you have a printed phone book — a thousand pages, every surname in order — and you need Nakamura.
You do not start at page one. Nobody in history has ever started at page one. You open it near the middle, land in the M's, and instantly throw away five hundred pages without reading a single name on them. Then you open the remaining half near ITS middle, land in the R's, and throw away two hundred and fifty more.
You did not decide those pages were unhelpful. You never looked at them. You knew from ONE glance that the name could not be there, because the book was in order — and being in order is what makes a single glance capable of eliminating half a book.
Checking one at a time removes one possibility per look. Halving removes half the remaining possibilities per look. That difference is the whole episode.
I am thinking of a number between 1 and 100. After each guess I will only tell you higher or lower. Do not guess cleverly — just guess the middle of whatever is left, every single time, and watch the last column.
New game: my number is somewhere from 1 to 1,000, and you have been told nothing else. What is the best possible first guess?
This is the same game played on lists of different sizes. Read the shape of it, then read the numbers, and notice how flat it stays while the list gets astronomically bigger.
| How many things are in the list | Guesses needed when you halve each time |
|---|---|
| 10 | 4 |
| 100 | 7 |
| 1,000 | 10 |
| 1 million | 20 |
| 1 billion | 30 |
Look at the last two bars. The list got a thousand times bigger and the work went up by ten guesses.
Now picture the bar that is missing — the one for checking a billion things one at a time. At this scale it would be about thirty million times taller than the tallest bar drawn. It does not fit on the page, on the wall, or in the building.
That is the gap. Not a bit faster. A different kind of thing entirely.
All of this rests on one condition, and it is a demanding one: the list has to already be in order.
The moment it is not, every glance stops meaning anything. If the phone book's names are shuffled, opening it in the middle and finding Mendez tells you precisely nothing about where Nakamura is — it could be anywhere, on any page, and you are back to reading the whole book.
So the speed is not free and it was not invented at the moment you pressed the key. Somebody sorted that data earlier, and sorting a billion things is genuinely hard work. Every time something new is added, the order has to be maintained, and that costs a little too.
This is one of the great trades in all of computing: do the work early, once, so the work later becomes almost nothing. Every index at the back of a book, every contacts list, every search box you have ever used is somebody paying that price up front on your behalf.
An app searches its list of names by halving, and it is instant. A new user signs up, so the app adds their name to the very end of the list. What happens to searching?
You’re previewing as a parent — nothing here is recorded.
The guess counts are arithmetic rather than measurement. Halving a range of n possibilities identifies the answer in at most ceil(log2(n+1)) guesses: 4 for 10, 7 for 100, 10 for 1,000, 20 for 1,000,000 and 30 for 1,000,000,000. Each of these can be checked against the powers of two 2^4 = 16, 2^7 = 128, 2^10 = 1,024, 2^20 = 1,048,576 and 2^30 = 1,073,741,824. The worked game is a real play-through: with the target 73 and the rule 'always guess the middle of what remains', the guesses are 50, 75, 62, 68, 71, 73 — six guesses, against the seven that the worst case for a range of 100 allows. The 'missing bar' comparison: checking a billion items one at a time is a billion steps against 30, a ratio of about 33 million to one. Drawn at the same scale as a 30-unit bar, the one-at-a-time bar would be roughly 33 million times taller. This method is called binary search, and the requirement that the data be sorted first is a standard part of its definition — an unsorted list makes the comparison at each step uninformative. Maintaining sorted order on insertion is the cost paid in exchange, which is the classic preprocessing trade behind database indexes.