Halving the Search Space

You're told to guess a number between 1 and 1,000 that someone else is thinking of. Each guess, you're told only "higher" or "lower." What's the fewest guesses that guarantees you find it, no matter how unlucky you are?

Try it yourself before reading on. The natural instinct for many people is to start low and creep up — guess 1, then 2, then 3 — which works but can take up to 999 guesses in the worst case. The fix, and the technique behind an enormous share of interview puzzles, is to always split the remaining possibilities as evenly as you can.

Why the middle, not the edge

Every guess gives exactly one of two answers: higher or lower (ignoring the lucky case of guessing correctly). Guessing near an edge of the remaining range wastes the guess — if you guess 2 out of a range of 1 to 1,000 and hear "higher," you've barely learned anything; 998 numbers remain. Guess the midpoint instead, and whichever answer comes back, you've eliminated roughly half the candidates in one shot.

Starting with 1,000 candidates and guessing 500: if "higher," 500 candidates remain (501–1000); if "lower," 499 remain. Either way you're down to about half. Repeating this — guess the midpoint of whatever range is left — brings the candidate count from 1,000 to 500 to 250 to 125 to about 63, 32, 16, 8, 4, 2, 1. That's ten guesses.

The general count: with $g$ guesses, each with two possible outcomes, you can distinguish at most $2^g$ starting possibilities. You need $2^g \geq 1000$, and $2^9 = 512$ is too small while $2^{10} = 1024$ clears it — so 10 guesses is both necessary and sufficient, and the halving strategy achieves that bound exactly.

Worked example: guess a number in [1, 1000]

Target is 743 (you don't know this). Guess 500 → "higher" (range becomes 501–1000, 500 candidates). Guess 750 → "lower" (range becomes 501–749, 249 candidates). Guess 625 → "higher" (626–749, 124 candidates). Guess 687 → "higher" (688–749, 62 candidates). Guess 718 → "higher" (719–749, 31 candidates). Guess 734 → "higher" (735–749, 15 candidates). Guess 742 → "higher" (743–749, 7 candidates). Guess 746 → "lower" (743–745, 3 candidates). Guess 744 → "lower" (743, 1 candidate). You've found it in 9 guesses here — comfortably inside the 10-guess worst-case bound, because the range didn't always split perfectly evenly.

The transferable technique

Whenever a puzzle lets you ask a query with a small, fixed number of possible answers, count how many total possibilities that query set can distinguish — that gives a lower bound on the number of queries needed. Then design each query to split the current remaining candidates as evenly as possible across the possible answers, not to test a specific guess you have a hunch about. This single idea — halve, don't guess — reappears in searching sorted arrays, in the egg-drop problem, in finding a median with few comparisons, and in any "find the different one in $n$ items" weighing puzzle.