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

Crew Quest

Crew Quest: Higher or lower
// Cut it in half
⏱ about 15 min

Crew Quest: Higher or lower

It is game night on the ship. Raven thinks of a number from 1 to 100.

Rocket guesses 50. "Lower," says Raven. He guesses 25. "Higher."

Rocket keeps halving, and he finds it in six guesses. "What do you notice about my guesses?" he asks proudly.

Raven grins. "You always picked the middle of what was left."

Nova cheers. "Here is a hint for the next round. Count your guesses. Can anyone ever need more than 7?"

  1. Binary search only works on a sorted list.
  2. Check the middle. Keep the half that could hold the target.
  3. mid = (low + high) // 2. Then move low to mid + 1, or high to mid - 1.
  4. Doubling the list adds just one check in the worst case.
  5. For 64 items, binary search needs at most 7 checks. Linear search may need 64.
◇ HIGHER OR LOWER
One person thinks of a whole number from 1 to 100 and writes it down secretly.
The other person guesses. The answer is only higher, lower or got it.
Keep a tally of guesses.
Play three rounds each. Try always guessing the middle of what is left.
Did anyone need more than 7 guesses?
For a grown-up
With halving, 7 guesses are always enough for 1 to 100. If a round takes more, look at the guesses together and find where the middle was skipped.
RECAP QUESTION
  • Read the question.
  • Tap your answer.
What must be true about a list before binary search can work?
Bonus recap statementTrue or false?
Binary search checks the middle first.?
Binary search works on jumbled lists.?
mid = (low + high) // 2.?
Doubling the list adds one check in the worst case.?
WHY THIS EXERCISEThese four facts sum up binary search.
What is (3 + 8) // 2?
Binary search worst case for 16 items?
Linear search worst case for 16 items?

Quest complete! Next week we sort star cards by hand.

← Friday