On this page
Predict first. A friend picks a whole number from 1 to 1000, and you may only ask yes or no questions. What is the fewest questions guaranteed to find it, however unlucky you are? Write your guess down, then test it.
Why does halving find the number fastest?
Each answer splits the numbers still possible into a "yes" group and a "no" group. You cannot know which answer is coming, so make the groups equal. Then, whatever the answer, you throw away half.
This is binary search. The NIST Dictionary of Algorithms and Data Structures defines it as searching a sorted array "by repeatedly dividing the search interval in half".
Here is a full game with the secret number 737, always asking "Is it more than the middle?"
More than 500? Yes: 501 to 1000 (500 left).
More than 750? No: 501 to 750 (250 left).
More than 625? Yes: 626 to 750 (125 left).
More than 688? Yes: 689 to 750 (62 left).
More than 719? Yes: 720 to 750 (31 left).
More than 735? Yes: 736 to 750 (15 left).
More than 743? No: 736 to 743 (8 left).
More than 739? No: 736 to 739 (4 left).
More than 737? No: 736 to 737 (2 left).
More than 736? Yes: only 737 is left.
Ten questions, and no other secret number needs more.
How many guesses do you need for 1 to 100: is it really 7?
Yes. In the classic version you say a number and hear "higher", "lower" or "correct". Start at 50, then 75 or 25, and keep guessing the middle. The Mobile CSP binary search lesson works it out: log₂ 100 = 6.6438, which rounds up to 7 guesses.
The rounding up matters. Six halvings of 100 can leave two numbers, so a seventh guess is needed to be sure. The Wikipedia article on binary search gives the worst case as ⌊log₂(n) + 1⌋ steps, which for 100 numbers is 7. For 1 to 100 and 1 to 1000, the higher-lower game and the pure yes or no game give the same answers: 7 and 10.
Where do logarithms come in?
The logarithm to base 2 answers one question: how many times can you halve a number before you reach 1?
Claude Shannon built information theory on this link. In his 1948 paper A Mathematical Theory of Communication, he wrote that with base 2 the units of information "may be called binary digits, or more briefly bits, a word suggested by J. W. Tukey". Each well-chosen yes or no answer gives you one bit.
The same paper gives a handy conversion: log₂ M = 3.32 log₁₀ M. So log₂ 1000 ≈ 3.32 × 3 ≈ 9.97, which rounds up to 10. Check it with powers of 2: 2¹⁰ = 1024 is the first one above 1000.
Use the conversion to predict other ranges:
1 to 10: about 3.32, so 4 questions (2⁴ = 16).
1 to 100: about 6.64, so 7 questions (2⁷ = 128).
1 to 1000: about 9.97, so 10 questions (2¹⁰ = 1024).
1 to 10 lakh: about 19.9, so 20 questions (2²⁰ = 1,048,576).
1 to 1 crore: about 23.3, so 24 questions (2²⁴ = 16,777,216).
Each time the range grows ten times, you need only about 3.32 more questions. That slow growth is what "logarithmic" means. Halving is the mirror image of doubling, which is why paper gets thick so fast in our post on how many folds it would take to reach the moon.
What makes a guessing strategy slow?
Checking numbers one at a time is a linear search, which in the worst case needs as many checks as there are items.
Counting up: "Is it 1? Is it 2?" can take 999 questions for 1 to 1000.
"Is it exactly 500?": a "no" removes just one number.
Lopsided splits: "Is it below 100?" A "no" still leaves 901 numbers.
A good question is one whose answer you truly cannot predict.
Try it at home: a 15-minute experiment
Everyone writes a prediction for the worst case in 1 to 100 and in 1 to 1000.
Play five rounds of 1 to 100 guessing any numbers you like. Record the counts.
Play five rounds always guessing the middle of what is left. Record again.
Compare your highest counts with 7, then play 1 to 1000 and compare with 10.
Ask: what range could you always crack in 12 questions? (Up to 2¹² = 4096.)
Parents: as the chooser, ask "How many numbers are still possible?" after each answer.
For the history, read about Virasena's ardhaccheda, counting halvings as an early logarithm, or use the same base-10 trick to find how many digits 2 to the power 100 has.
The Fermi Simulation Lab has interactive simulations for ideas that are easier to see than to read. If logarithms feel shaky, the Fermi Concept Library gives every concept in mathematics its own lesson and its place in the map.
