← Back to course
Code Crew G5 / Week 06 / Crew Quest
6/6
Week 06 · Search one by one

Crew Quest

Crew Quest: Flip and find
// Linear search and counting checks
⏱ about 15 min

Crew Quest: Flip and find

Raven lays eight cards face down in a row. Each card has a made-up star name on the back.

"Find the card that says Lumen," she tells Rocket.

Rocket flips cards one at a time from the left. Raven keeps a tally of every flip.

"Seven flips!" Rocket says. "What do you notice if Lumen were first?"

Nova hums. "Here is a hint. Try hiding the target in different spots, and compare the tallies."

  1. Linear search checks items one by one from the start.
  2. It returns the spot when it finds the target, or -1 when it does not.
  3. Checks equal the spot number plus 1.
  4. Best case: 1 check. Worst case: one check per item.
  5. Say not found only after the loop has checked every item.
◇ FLIP AND FIND
Write a made-up star name on each of eight paper cards.
One person shuffles them and lays them face down in a row.
The other person picks a target name and flips cards from the left.
Keep a tally of every flip until the target appears.
Play four rounds. Write down the fewest and the most flips.
For a grown-up
Point out that the order of the cards, not the player, decides the number of flips. That is the idea of best and worst case.
RECAP QUESTION
  • Read the question.
  • Tap your answer.
Eight face-down cards. What is the most flips a linear search could need?
Bonus recap statementTrue or false?
Linear search checks items in order.?
The worst case for 8 cards is 4 flips.?
Checks equal the spot number plus 1.?
A missing target is a worst case.?
WHY THIS EXERCISEThese rules let you predict how long any linear search takes.
A target is in spot 5. How many checks?
What is the best case number of checks for 1,000 items?
What does find return when the target is missing?

Quest complete! Next week we learn a search that cuts the list in half every time.

← Friday