Week 07 · Search, Speed and Limits

Wednesday

Beacon Lab: Thirty-two cards

// Binary search, counting steps, heuristics and problems no algorithm can solve

⏱ about 20 min

Wednesday: Beacon Lab: Thirty-Two Cards

Mission control wants Beacon to answer search questions quickly, even when the log gets long.

Comet deals thirty-two paper cards face down in a long row, numbered 1 to 32 in order.

"Pick a secret number," she tells Wren. "I bet I can find it in fewer than ten guesses."

Wren writes a number on a sticky note and hides it. "Go ahead. I will only say higher, lower or found."

Nova hovers above the row. "Interesting," she says. "Count how many cards are still in play after each guess."

Comet flips over card 16. "Guess one."

Your mission

You will play guess-the-number with sorted cards, using binary search.

You will record how many cards are left after each guess, then find the most guesses this game can ever need.

32 small paper slips or index cards
A pencil and a sheet of paper for your trace table
A partner to pick the secret number (or pick one yourself and cover it)

Number the cards 1 to 32 and lay them face down in order.
Your partner secretly chooses one number from 1 to 32.
Guess the middle card using the crew's rule: low plus high, divided by 2, rounded down. Your first guess is 16.
Your partner says higher, lower or found.
Push away every card that cannot be the secret number.
Write down the cards still in play, then guess the middle of those.
Repeat until you find the number. Count your guesses.
Play three rounds. Then play one round of linear search, guessing 1, 2, 3 and so on.

A sample trace: the secret number is 23

Guess	Cards in play	You guess	Partner says	Cards left after
1	1 to 32	16	Higher	17 to 32 (16 cards)
2	17 to 32	24	Lower	17 to 23 (7 cards)
3	17 to 23	20	Higher	21 to 23 (3 cards)
4	21 to 23	22	Higher	23 only (1 card)
5	23 only	23	Found	Done

PREDICT, THEN PLAY TO CHECK

Read the question.
Tap your answer.

With 32 cards and the round-down rule, what is the most guesses binary search could ever need?

Which secret number needs all 6 guesses: 16, 24, 28, 30, 31, then itself?

How many guesses does secret number 16 need?

With linear search, guessing 1, 2, 3 and so on, what is the most guesses you could need?

Count the halvings in the worst case: 32, then 16, 8, 4, 2 and 1 card in play.

That is five halvings. One more guess on the last card makes six guesses at most.

What the lab shows	True or false?
Each binary search guess eliminates about half of the cards in play.	?
Binary search would still work if the cards were shuffled.	?
Binary search never needs more than 6 guesses for 32 sorted cards, using this rule.	?
Linear search never needs more than 6 guesses for 32 cards.	?

WHY THIS EXERCISEYour card game is binary search: sorted data, a middle guess, and half eliminated each time.

Copy your three trace tables. Which secret number took you the most guesses, and why?If the row had 64 cards instead of 32, how many guesses do you predict at most? Explain.Write two sentences for Beacon's design notes: when should Beacon use binary search, and when linear search?

Great lab work. Tomorrow you will meet problems that even fast computers find hard.

Grown-up checked my answers

← Tuesday Thursday →