The Twenty-Question Machine

Somewhere behind every search bar, autocomplete, and database index you've ever used sits an idea a child already knows: when someone says “guess my number, I'll say higher or lower,” you don't start at 1. You start in the middle. Every answer — higher, lower — destroys half of everything that's left. That's the entire algorithm. The rest of this essay is just watching that one move, very closely, until it stops looking like a trick.

Play it first. Then we'll slow the machine down to one line of code at a time.

Exhibit A · Guess my number

I'm thinking of a number between 1 and 100. If you halve cleverly, how many guesses do you need — worst case?

Slide and guess. The shaded region is where my number can still be hiding. Par is 7.

1255075100

Six billion humans play this game as children. Your move.

Observe The shaded region halves with every answer — 100 → 50 → 25 → 12 → 6 → 3 → 1. Seven halvings crush a hundred possibilities, because halving is exponential decay of your ignorance. Hold onto the shape of that: log₂(100) ≈ 6.6, so ⌈7⌉ guesses, guaranteed — no luck required.

§1Now watch the interpreter play it

Ten lines of code play the same game against a sorted shelf of numbers. Below, you get the view the machine has: the exact line being executed, every variable it's juggling, and the shelf with its live pointers — lo, hi, and their midpoint mid. Faded books are provably eliminated: the code will never look at them again.

Exhibit B · The interpreter's eye

The shelf holds 15 numbers. Worst case, how many comparisons before the loop ends?

Click a book to make it the target (or take the unlucky pick), then ⏭ step through the code line by line.

target — 42

ready

lo mid hi

lo	—
hi	—
mid	—
arr[mid]	—
target	42
comparisons	0
still possible	15 books

Pick a target, press step. The interpreter will tell you what it's looking at.

Observe Watch what the two pointer moves mean: lo = mid + 1 is the code saying “everything left of here is now impossible” — it never re-checks, never doubts. Four comparisons, maximum, for fifteen books (⌈log₂ 15⌉ = 4). And the unlucky pick matters: the loop ends with lo crossing past hi — the honest way to say “not here” without checking every book.

Note: (lo + hi) >> 1 is integer halving. Fun scar tissue: for ~20 years most real-world implementations carried an overflow bug in exactly this line.

§2The part that feels illegal

Fifteen books is cute. The reason binary search runs the world is what happens when the shelf stops being cute. Halving doesn't care how big the pile is — it only cares how many times the pile can be halved. And that number grows absurdly slowly.

Exhibit C · One guess per second

A billion sorted items. How many halvings to corner any one of them?

Drag the shelf size and watch the two strategies race — at one check per second, human speed.

shelf size — 1,000 items

check every book

halve the shelf

Observe Double the shelf and linear search doubles its pain — but halving just needs one more guess. That's the whole asymmetry: n versus log₂ n. It's why a database finds your row in a table of billions before your finger leaves the Enter key, and why "sort it once, search it forever" is one of the oldest bargains in computing.

Bars share one linear scale, so the linear bar gets clipped at plate's edge on big shelves — the label says so. Steps shown are worst case.

§3The fine print that bites

Binary search's power comes from one assumption so load-bearing it's easy to forget: the shelf must be sorted. Every elimination — “the target can't be left of here” — is only true if order holds. Break the assumption and the algorithm doesn't crash, doesn't warn, doesn't slow down. It does something much worse: it answers quickly and wrongly.

Exhibit D · The unsorted shelf

The number 23 is on this shelf — you can see it. Unsort the shelf, run the search, and watch the machine swear it isn't there.

shelf SORTED

lomidhi

Observe On the shuffled shelf the search returned “not found” in 4 steps — while 23 sat in plain sight. It faded books that secretly contained the answer, because "everything left of here is smaller" was a lie. Same failure family as essay № 1's hallucinating model and № 2's doom loop: a system being confidently wrong because a precondition quietly broke. Fast algorithms don't check your assumptions. That's your job.

So when does the naive scan win? Tiny shelves, or a single one-off search — sorting first costs n·log n, which only pays for itself if you'll search again. Everything in engineering is a bargain.

§4What to keep

Binary search = the kid's guessing game, formalized: halve your ignorance every step.
The cost is log₂ n — a billion items, thirty questions. Doubling the data costs one more question.
The two pointer moves are proofs of elimination, not guesses — which is exactly why the sorted precondition is sacred.
Broken preconditions don't crash; they produce fast, confident garbage. Check them.

This is the third essay in a row where the villain was confident wrongness — a model without sources, a loop without limits, a search without its precondition. The pattern is the lesson: speed and confidence are cheap; verified answers are engineering.

← previously: № 1 · How RAG finds the answer · № 2 · Inside the loop

Nawa — full-stack AI engineer. By day I build RAG systems and agent loops; this series is an experiment in essays you operate instead of read. If you stepped the interpreter and something clicked that a lecture never managed — that's the bet paying off.

Portfolio GitHub X / Twitter Hire me

Colophon — The interpreter view is a real trace of the code shown, precomputed so stepping is instant; the guessing game's number is honestly random per visit. Simplifications: the shelf is tiny and the "one guess per second" race is a dramatization of worst-case counts. Built with agent assistance; every interaction hand-verified.