← Back to course
Python 11-12 / Week 08 / Mission Quest
6/6
Week 08 · Searching

Mission Quest

Mission Quest: Higher or lower
// Linear search checks each item; binary search halves sorted data
⏱ about 30 min

Saturday: Mission Quest: Higher or Lower

On Saturday the crew plays a guessing game in the maker space. Comet thinks of a number from 1 to 100. Wren guesses, and she answers only "higher" or "lower".

Wren starts at 1, then 2, then 3. Comet groans. "This could take a hundred guesses!"

"What does the evidence say?" Wren asks, and changes his plan. "Fifty." Then "twenty-five." Then "thirty-seven." He has it in three.

Nova projects the number line shrinking by half after each answer. "How can I help?" she asks. "That is binary search with people. Count the guesses."

Comet points at you. "Lead programmer, try it with your family."

◇ HIGHER OR LOWER
You need: paper and a pencil for each player.
1. A family member secretly writes a number from 1 to 100.
2. You guess. They answer only "higher", "lower" or "got it". Tally each guess.
3. Play once guessing in order from 1 upward, for as long as you both have patience. Then play again, always guessing the middle of what is left.
4. Swap roles, so they guess and you answer. Compare the tallies.
5. Together, find a secret number that the middle strategy gets on the very first guess.
For a grown-up
This game is binary search: each answer lets the guesser throw away about half of the numbers left.
Ask your learner why "higher or lower" matters. With only "yes" or "no", the middle guess would not help.

Wren checked the middle strategy with a program that plays every secret number from 1 to 100.

# guess_count.py


def guesses(secret):
    """How many middle guesses find secret, from 1 to 100."""
    low = 1
    high = 100
    count = 0
    while True:
        guess = (low + high) // 2
        count += 1
        if guess == secret:
            return count
        elif guess < secret:
            low = guess + 1
        else:
            high = guess - 1


most = 0
for secret in range(1, 101):
    if guesses(secret) > most:
        most = guesses(secret)
print(guesses(50))
print(guesses(37))
print(most)
1
3
7
WEEK 8 RECAP
  • Read the question.
  • Tap your answer.
With the middle strategy, what is the most guesses any secret from 1 to 100 needs?
Guessing 1, 2, 3 in order is which search?
What does binary search need before it can start?

Wonderful searching this week. Next week the crew sorts the catalog, so binary search has sorted data to work on.

← Friday