I'm thinking of a number between 1 and 1,000,000. You may ask yes-or-no questions of the form "is it higher than this?" How many do you need? A million would be the honest answer if you guessed one by one. The real answer is 20. That trick is called binary search, and it is how a phone finds a contact, a database finds a row and a program finds a word in a sorted list.
Suppose the list is sorted. Look at the item in the middle. If it is the one you want, you are done. If your target is bigger, everything on the left is out, and so is the middle itself. If it is smaller, everything on the right is out. Either way, half of the candidates disappear with a single look.
Then do it again on what is left. A million becomes 500,000, then 250,000, then 125,000. After 20 looks only one candidate remains. The number of looks is how many times you can halve the list before reaching one, and that is the base-2 logarithm, rounded up.
Below, a secret number is hidden in the grid. Tap any cell to guess it. You are told "higher" or "lower", and cells that can no longer be the answer fade out. Try it your own way first, then press the halving button and watch what changes.
Tap a cell to guess. The lime outline marks the middle of what is still possible.
Guessing at random works, but it is slow and luck decides how fast you finish. Guessing the middle each time never needs more than the limit shown. Doubling the grid adds just one extra guess to that limit.
Because each look halves the list, the cost grows with the logarithm of the size, not the size itself. Doubling the list adds one step. Multiply it by a thousand and you add only about ten.
| Items in the sorted list | Looks needed (at most) |
|---|---|
| 1,000 | 10 |
| 1,000,000 | 20 |
| 1,000,000,000 | 30 |
| 8,000,000,000 | 33 |
So one name among every person on Earth takes about 33 looks. Checking one by one could take eight billion.
Binary search only works because "lower" and "higher" mean something. If the list were shuffled, the middle item would tell you nothing about which side your target is on. Sorting costs effort, so it pays off when you will search many times, which is exactly what a phone book, a dictionary or a database index is for.
The idea is easy to say. Writing it correctly was not. Jon Bentley noted that the first binary search was published in 1946, but the first version that worked for every list size did not appear until 1962.
Even later it slipped through. The version in Bentley's book Programming Pearls hid a bug for about twenty years. In 2006 Joshua Bloch wrote that the same bug had sat in the Java library he helped write for roughly nine years. The culprit was one line that finds the middle:
mid = (low + high) / 2
If the list is huge, low plus high can be larger than the biggest number a 32-bit integer can hold (2,147,483,647). The sum wraps around to a negative number, and the program looks at a position that does not exist. It needs arrays of about a billion items or more, which is why it stayed hidden for so long. The fix is to measure from the left edge instead:
mid = low + (high - low) / 2
Same middle, no overflow. A one-line change, after decades.
Sorted list, look in the middle, throw away the wrong half, repeat. Twenty looks cover a million items and thirty cover a billion.