Mansori

Guess My Number in 7 Tries

About this lesson, for parents and teachers

I am thinking of a number from 1 to 100. You only get 7 guesses, and I will only say "too high" or "too low". Is that even possible? It is, with one clever trick.

Ages 9–11 · about 6 minutes · builds on Counting With Light Bulbs: Binary

Try this

  1. Drag the marker along the number line (or use −1 and +1), then press Guess.
  2. After each answer, the numbers that cannot be right go grey and the line zooms in. Try to always guess the middle.
  3. Beat 1 to 1000 in only 10 tries.
  4. Then pick a secret number for the computer and watch it find your number with binary search.

How it works

If you guess 1, then 2, then 3, you might need 100 guesses. But if you guess the middle, 50, then "too high" or "too low" throws away half of the numbers at once. Whatever the answer, only about 50 numbers are left. Guessing in order like 1, 2, 3 is called linear search: it works, but it is slow.

Keep doing it. 100 numbers become 50, then 25, then 13, 7, 4, 2 and finally 1. That is 7 halvings, so 7 guesses are always enough for 1 to 100. This strategy is called binary search, because each guess splits the numbers into two parts. Even if you are unlucky every single time, the middle guess always leaves the smaller half or an equal half.

The amazing part is what happens with bigger ranges. 1 to 1000 needs only 10 guesses, and 1 to a million needs only 20. Doubling the numbers adds just one more guess. Mathematicians call the number of halvings the logarithm (base 2), and it grows very slowly. That is why binary search is one of the most famous algorithms in computer science.

Binary search only works when things are in order. "Too high" only tells you something useful because the numbers are sorted from small to big. That is why computers often sort data first: once it is sorted, finding anything becomes super fast. A dictionary is sorted from A to Z, which is why you can open it near the middle and jump towards the word you want.

Where engineers use this

Databases, phone contact lists and search engines use binary search on sorted data to find one item among millions in a few steps. Programmers even use it to find which change broke their code, with a tool called git bisect.

Words to know

Binary search
Finding something in a sorted list by checking the middle and throwing away the half it cannot be in, again and again.
Range
All the numbers that could still be the answer, like 26 to 49.
Halving
Cutting something into two equal parts. Each good guess halves the range.
Sorted
Arranged in order, like 1, 2, 3 or A to Z. Binary search needs sorted data.

Talk about it

Goal: Find a number from 1 to 100 in at most 7 guesses by cutting the range in half each time.

  • How would you find a word in a paper dictionary? Is that like binary search?
  • If someone picked a number from 1 to 2000, how many guesses would you need?
  • Why would binary search fail if the numbers were all mixed up?

Without a screen: Play guess my number at dinner: one person picks a number from 1 to 100 and only answers "higher" or "lower". Keep score of the guesses. Then try finding a page number in a thick book by opening it in the middle and halving.

Curriculum links: CSTA K-12 1B-AP-08 (compare and refine multiple algorithms for the same task); AP Computer Science Principles AAP-2.P (binary search)

Questions

What is binary search in simple words?
Binary search is a way to find something in a sorted list by always checking the middle. Each check throws away half of what is left, so you find the answer very quickly.

What is the best strategy for guess my number from 1 to 100?
Always guess the middle of the numbers that are still possible: start with 50, then 25 or 75, and so on. This never needs more than 7 guesses.

Why is binary search so fast?
Every guess halves the range, so the number of guesses only grows by one when the range doubles. A million sorted items need only about 20 checks.