How can 20 guesses find one number in a million?

A game first

I’m thinking of a whole number between 1 and 1,000,000. Guess it. After each guess I’ll tell you higher or lower, and you have twenty guesses. Type one below, or let me play while you watch.

Before you read on: with the best possible strategy, how many guesses do you need to be sure of finding the number, whatever it is?

Twenty guesses are always enough, if every guess cuts the possibilities in half. Guess 500,000 and hear higher, and half a million numbers vanish in one go. Guess the middle of what’s left, and half of that goes. Twenty halvings take a million to one.

Halving is doubling, backwards

Turn the game upside down. With one guess you can only win if you happen to say the right number, so one guess covers one number. With two guesses, the first one splits the rest: one number lower, one higher, so two guesses cover three. Every extra guess doubles what you can reach, plus the one you say. Here are all the games that the halving strategy can play, as a tree of guesses.

A list of 1 million numbers needs 20 guesses. Drag that number. Ten times bigger costs only about three more guesses, a thousand times bigger costs ten, because 2¹⁰ = 1,024.

Mathematicians call the number of halvings the base-2 logarithm, written log₂ n. Checking the numbers one at a time takes about n/2 tries on average when the number is there and equally likely to be anywhere (and all n when it isn’t there at all), while binary search takes about log₂ n either way. For a million that is 500,000 against 20; for a billion, 500 million against 30.

Searching a sorted list

The game works on anything kept in order: words in a dictionary, names in a phone book, numbers in a sorted list. A program keeps two fingers on the list, lo and hi, the first and last places the answer could still be. It looks at the middle, and moves one finger past it. Here it is looking for 42.

Step 1 of 16. The fingers start at both ends: lo = 0, hi = 14.

Each red part of the code is a switch. Click one and run again. They are three classic boundary traps. When Jon Bentley gave professional programmers a couple of hours to write a binary search, about nine out of ten then found bugs in their own code.¹ Donald Knuth counted sixteen years between the first published binary search, in 1946, and the first one without a bug.²

The bug that waited nine years

The line mid = (lo + hi) // 2 is safe in Python, where whole numbers can grow as large as they like. In Java an ordinary int has exactly 32 bits, and its largest value is 2,147,483,647. Add two big positions, 1,500,000,000 and 1,600,000,000, and the sum runs off the end and wraps around to the negatives, like a car’s odometer. (In C it is worse: the language doesn’t fix the size of an int, and running past its end is undefined behaviour, so the program may do anything at all.)

Here 1,500,000,000 + 1,600,000,000 should be 3,100,000,000, but Java’s 32-bit int wraps it to −1,194,967,296, so mid comes out as −597,483,648, and looking up a negative position crashes the program. Joshua Bloch wrote the binary search in Java’s own library, and it had this very line, the same one as in Jon Bentley’s carefully proved version. It sat there for about nine years, until it broke someone’s program and was reported in 2006: it bites only on lists of about a billion elements or more.³ The fix is to never add the two: mid = lo + (hi - lo) // 2 stays in range for every list that fits in memory.

Wait, but then…

Binary search isn’t really about lists. It works on any question where too low and too high make sense. When a program breaks somewhere among its last thousand changes, git bisect finds the guilty one in ten tests. The game Twenty Questions works for the same reason: twenty yes-or-no answers can tell apart about a million things, if each question splits what’s left in half. So here is one to take away: imagine a dictionary of 170,000 words. How many yes-or-no questions do you need to find any one of them?

Try it yourself

Each task ticks itself off when the page above shows it.

1. Win the game in twenty guesses or fewer.Every guess at the middle of what’s left halves it, and twenty halvings always reach one.
2. Change one switch in the code so it can loop forever.With lo = mid, once only two places are left, mid lands on lo, lo never moves, and the loop never ends.
3. Find a number that while lo < hi can’t find, even though it’s in the list.When one place is left, lo equals hi, the loop stops, and that last place is never checked.
4. Make the list so long that it needs exactly forty guesses.Forty guesses cover 2⁴⁰ − 1 numbers: just over a trillion. Thirty-nine cover about half that.
5. In your own words: why does doubling the list only add one guess?

So twenty guesses find one number in a million because every guess at the middle throws away half of what is left, and a million can only be halved twenty times before nothing is left to throw away.