How to find one name among a billion in 30 looks: binary search
30seconds
Pick a number from 1 to 1,000,000 and you can find it in at most 20 yes-or-no questions. The trick is binary search: look in the middle of a sorted list, throw away the half that cannot hold your target, and repeat. Every look halves the problem, so doubling the list adds only one extra step.
Play it yourself in a grid, then see why a one-line way of finding the middle hid a bug in famous code for years.
Deep dive · 4 min
More in Computing
View all →
Why common letters get short codes in a ZIP file: Huffman coding
ASCII spends 8 bits on every letter, whether it is a common e or a rare z. In 1951 a graduate student, David Huffman, found a way to give frequent symbols…
How a computer finds one flipped bit and fixes it: Hamming's code
A bit can flip in memory, on a disk or in a radio signal, and nothing tells you which one went wrong. In 1950 Richard Hamming published a code that finds the…
Why 0.1 + 0.2 isn't 0.3: flip the 64 bits a computer uses for decimals
Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. Nothing is broken. Computers count in powers of two, and a tenth is an…
How a Bloom filter says "definitely not" using just a few bits
How can a computer check whether a word is on a huge list using only a few bits per entry? A Bloom filter flips a handful of switches for every word you add…
How one extra digit on your bank card catches your typos
The last digit of your bank card number isn't part of your account. It's a check digit, computed from the other fifteen by a recipe an IBM engineer patented in…
How computers fake grey using only black and white dots
Old Mac screens, cheap printers and some modern games can only show two colours: black and white. Yet they still draw soft shadows and smooth skies. The trick…