← Back to course
Code Crew G5 / Week 07 / Monday
1/6
Week 07 · Binary search

Monday

Guess my number
// Cut it in half
⏱ about 15 min

Monday: Guess my number

On a quiet evening, Nova invents a game. "I am thinking of a whole number from 1 to 100," she says. "I will say higher or lower."

Rocket jumps in. "Is it 1? Is it 2? Is it 3?" Nova keeps saying higher.

Raven laughs kindly. "What do you notice? Each guess only rules out one number."

Rocket rubs his chin. "What guess would rule out the most numbers?"

Nova winks a cyan eye. "Here is a hint. Try a guess right in the middle."

Halve it every time

If the first guess is 50 and Nova says higher, every number from 1 to 50 is gone. Half the numbers vanish with one guess!

Then guess the middle of what is left. Keep halving until you land on the number.

GuessNumbers still possibleNova says
501 to 100higher
7551 to 100lower
6251 to 74higher
6863 to 74higher
7169 to 74lower
6969 to 70higher
7070 to 70got it!

Nova was thinking of 70. Halving found it in 7 guesses. Guessing 1, 2, 3 would have taken 70 guesses.

PLAY THE HALVING GAME FROM 1 TO 100.
  • Read the question.
  • Tap your answer.
You guess 50. Nova says lower. Which numbers are still possible?
Next you guess 25. Nova says higher. Which numbers are left?
After your first guess of 50 and the answer higher, how many numbers are still possible?
WHY THIS EXERCISEA middle guess throws away about half of the numbers in one step.
StatementTrue or false?
Guessing in the middle removes about half the numbers.?
Guessing 1, 2, 3 in order is just as fast.?
Halving only works because Nova says higher or lower.?
WHY THIS EXERCISEThe higher or lower clue is what lets us throw away a whole half.

Practice lab: halving from 1 to 20

Play again with the numbers 1 to 20. The secret number is 13. Always guess the middle of what is left.

GuessNumbers still possibleNova says
101 to 20higher
1511 to 20lower
1211 to 14higher
1313 to 14got it!
After guess 10 and higher, how many numbers are still possible?
After guess 15 and lower, how many numbers are still possible?
After guess 12 and higher, how many numbers are left?
How many guesses did it take in all?
HALVING CHECK
  • Read the question.
  • Tap your answer.
From 1 to 100, you guess 50 and hear higher. What is the best next guess?
From 1 to 10, you guess 5 and hear lower. How many numbers are left?
Which clue lets you throw away half the numbers?
StatementTrue or false?
A middle guess is a smart first guess.?
Guessing 1 first throws away half the numbers.?
After each guess, the numbers left are about half as many.?
Halving found 13 in fewer than 13 guesses.?
WHY THIS EXERCISEHalving shrinks the problem fast. Counting one by one does not.
You start with 64 numbers. After one middle guess, about how many are left?
WHY THIS EXERCISEA middle guess throws away about half.

Brilliant guessing! Tomorrow we use halving to search the sorted star catalog by hand.