← Back to course
Intro to CS 9-10 / Week 07 / Mission Quest
6/6
Week 07 · Search, Speed and Limits

Mission Quest

Mission Quest: Guess my number to 100
// Binary search, counting steps, heuristics and problems no algorithm can solve
⏱ about 20 min

Mission Quest: Guess My Number to 100

The rover is parked, the readings are logged, and the crew has a free evening in the greenhouse.

Comet writes a secret number from 1 to 100 on a leaf-shaped sticky note. "Bet you cannot find it in seven guesses."

Wren does not even blink. "Fifty," he says.

"Lower," Comet says.

"Twenty-five."

"Higher."

"Thirty-seven," Wren says. Comet sighs and turns the note around. It says 37.

Nova blinks three small blue lights, one for each guess. "Three guesses," she says. "Great discovery!"

"Binary search," Wren says, grinning. "Your turn to guess."

  1. A problem is a general task. An instance has specific input. A decision problem has a yes or no answer.
  2. Binary search starts at the middle of sorted data and eliminates half of it each check.
  3. Data must be sorted for binary search. On sorted data, it is often faster than linear search.
  4. Efficiency can be measured by counting steps as the input grows.
  5. Factorial growth takes unreasonable time, so people use heuristics. Some problems are undecidable.
◇ GUESS MY NUMBER TO 100
One player secretly picks a whole number from 1 to 100 and writes it down.
The guesser uses the crew's rule: guess low plus high, divided by 2, rounded down. The first guess is 50.
The picker answers only higher, lower or found. The guesser counts each guess.
Swap roles and play again. Who used the fewest guesses?
Round three: the guesser picks numbers at random, with no plan. Compare the count with binary search.
For a grown-up
Ask: why does guessing the middle work better than guessing at random?
Ask: binary search needs sorted data. What is sorted in our home, and what is not?
This course is unplugged. Your student never needs an app, an account or a website.
QUEST CHECK
  • Read the question.
  • Tap your answer.
For numbers 1 to 100, what is the first guess with the crew's rule?
The answer to 50 is lower. Which numbers are still in play?
With this rule, what is the most guesses any secret number from 1 to 100 can need?
On paper, draw a number line from 1 to 100. Shade the numbers still in play after each of Wren's guesses: 50, then 25, then 37.
What must be true about data before you can use binary search on it? Type one word.
WHY THIS EXERCISESorted data is the one thing binary search cannot do without.
← Friday