Computing · Binary search
How can you find one name among a million in 20 steps?
What you’ll see
A phone book holds a million names, in alphabetical order. Checking them one by one could take a million looks. Can you do better? Open it right in the middle. The name you want comes later, so the whole first half is gone. Half a million left. Open the middle of what remains, and halve it again. And again. Every look throws away half of what's left. Twenty halvings take a million down to one, because two to the twentieth is just over a million. A billion names? Only ten more looks.
