Guess my number in seven tries
Think of a number from 1 to 100 and let the computer guess. It always guesses the middle of what is left, and each “too high” or “too low” throws half the numbers away. Count its guesses and find the number that makes it work hardest.
Core concept
Halving the range each time finds any number from 1 to 100 in at most 7 guesses, because 7 halvings are enough to shrink 100 numbers to 1 (2⁷ = 128): the idea behind binary search
Topic: Algorithm efficiency
In the guessing game one player thinks of a number from 1 to 100, and the other guesses. After each guess the answer is “too high”, “too low” or “right”. Guessing 1, 2, 3 … could take 100 guesses. A smarter way is to guess the middle, 50. If 50 is too high, the number is between 1 and 49, so half the numbers are gone in one guess. Then guess the middle of what is left, and keep halving. A program does this with a while loop: Steps that repeat, either a set number of times or until something becomes true. All key words and two variable: A named box that holds a value the program can read and change. All key words, low and high: guess ← floor((low + high) / 2). Because 2 × 2 × 2 × 2 × 2 × 2 × 2 = 128 is more than 100, at most 7 halvings are ever needed.
What you will learn
- Trace a while loop that halves a range with low, high and a middle guess.
- Count the guesses the halving method needs for different secret numbers.
- Explain why 7 guesses are always enough for 1 to 100.
- Compare halving with guessing one number after another.
Before you start
- Know how a while loop and if / else work.
Materials
- A friend to play the guessing game with
Equipment
- None
Procedure
- Let the computer find 37 and read its guesses.
- Find a secret number that needs the most guesses.
- Step through a game and watch low and high close in.
- Answer the practice challenges.