- Learnt28 min · the search, and what it costs
- Basic24 min · find any card in your deck
- Challenge 1–327 min · the shortcut, by power, counting matches
- Extrabonus · giving up early
Review — where we got to 5 min
- Three lists in step: row 4 of each is one card.
(item # of [Bat] in [names v])reports a row number, or 0.- Best-so-far and running total are both one walk down a list.
Quick-fire
How does (item # of [Bat] in [names v]) know the Bat is in row 4?
Reveal the answer
It looks. Row 1, row 2, row 3, row 4 — comparing each one until it matches. Today you write that out in blocks, and it will be the first thing you build that has a name computer scientists use.
Today’s Topic 3 min
- Linear search — start at the top, compare, move down, stop when found
- Reporting where it was, and coping with it not being there
- Counting the looks: best case, worst case
- What the ready-made blocks do for you, and what they hide
Learning outcome
By the end of this lesson you will be able to:
- Write a linear search in Scratch blocks.
- Stop a loop as soon as the answer is found.
- Say how many comparisons a search took, and why.
Learnt — looking, one row at a time 28 min
1 · How would you do it?
Put the deck face up on a table and ask somebody to find the Frog. Watch what they do. They start at one end and go along, looking at each card until they see it.
That is linear search. It has a name because it is the most obvious way to find something, and because almost everything else is measured against it.
- Start at row 1.
- Is this row the one I want?
- If yes, remember the row number and stop.
- If no, go down one row.
- If you run off the end, it was not there.
2 · In blocks
The loop has to stop two different ways — found it, or ran out — so it is a repeat until <> with an <<> or <>> in it, exactly like the quiz in Lesson 3-8:
set [n v] to (0)
set [found at v] to (0)
repeat until <<(n) > ((length of [names v]) - (1))> or <(found at) > (0)>>
change [n v] by (1)
if <(item (n) of [names v]) = (looking for)> then
set [found at v] to (n)
end
end
found at starts at 0 and stays 0 if nothing matches — the same “0 means nowhere” you met last lesson.How to use this: Click the green flag and watch it check each card in turn, out loud, until it finds the Frog.
3 · Counting the work
Add one block — change [looked at v] by (1) — and the search tells you how hard it had to try:
| Looking for | Looks | Why |
|---|---|---|
| Dragon (row 1) | 1 | Found straight away — the best case. |
| Crab (row 6) | 6 | Last in the deck. |
| Unicorn (not there) | 6 | You cannot say “it is not here” until you have read every row. |
How to use this: Click the green flag and watch three searches report how many looks each one took.
Basic — find any card 24 min
Open your deck from last lesson.
Step 1 — the boxes
- Make
n,found atandlooked at. - Show the last two on the Stage.
Step 2 — ask what to look for
- Add
ask [Type a card name] and wait. - Set all three variables to 0 straight after.
Step 3 — the loop
- Build the
repeat until <>with the two-part stop. - Inside: bump
n, bumplooked at, then the if. - Add
switch costume to (item (n) of [pics v])so you can see it looking. - Add a short
wait (0.35) secondsso it is watchable.
Step 4 — report
- After the loop, if
found atis more than 0, show the card and its power. - Otherwise say it is not in the deck, and how many rows you read.
Step 5 — test both ends
- Search for the first card. Looks should be 1.
- Search for the last card. Looks should be 6.
- Search for something silly. Looks should be 6 and found at 0.
ask [Type a card name] and wait
set [n v] to (0)
set [found at v] to (0)
set [looked at v] to (0)
repeat until <<(n) > ((length of [names v]) - (1))> or <(found at) > (0)>>
change [n v] by (1)
change [looked at v] by (1)
switch costume to (item (n) of [pics v])
wait (0.35) seconds
if <(item (n) of [names v]) = (answer)> then
set [found at v] to (n)
end
end
if <(found at) > (0)> then
say (join [Row ] (join (found at) (join [, power ] (item (found at) of [powers v])))) for (3) seconds
else
say (join [No such card. I looked at all ] (join (looked at) [ of them.])) for (3) seconds
end
How to use this: Click the green flag, then click the stage once. Type Bat to find one, or Unicorn to watch it read the whole deck.
It always says “not in the deck”.
The if is comparing (item (n) of [pics v]) or the wrong list. It must compare the names list with the answer.
It finds the card but keeps going to the end.
The found at half of the stop test is missing, or it compares to the wrong thing. The loop must stop when found at goes above 0.
It misses the last card in the deck.
An off-by-one. The stop test should use ((length of [names v]) - (1)) because n is bumped inside the loop, not before the test.
The second search reports the first search’s row.
set [found at v] to (0) is missing before the loop.
The shortcut, and what it hides
Scratch has two blocks that do a search for you. Compare them with what you built.
<[names v] contains [Shark]?>— yes or no.(item # of [Shark] in [names v])— a row, or 0.- Say what each one can do that the other cannot, and what neither can do.
How to use this: Click the green flag and watch both blocks answer for a card that is there, then one that is not.
Teacher note
The honest answer is: use the block. The reason to write the loop is that item # of is a linear search with the lid on, and a pupil who has never lifted the lid thinks searching is free. That is the sentence worth saying.
Search by power
Find a card by its number instead of its name.
- “Which card has power 8?” — the answer is the Dinosaur.
- The loop is the same; only the question inside it changes.
- A power no card has is reported properly.
How to use this: Click the green flag and watch two searches: power 8, which exists, then power 6, which does not.
Teacher note
Ask them how much of the script they had to change. It should be one block — the comparison. That is the moment an algorithm stops being “a script I wrote” and starts being a shape you can reuse.
How many match?
Sometimes the first one is not what you want. Count them all instead.
- Give your deck three cards with the same power.
- Count how many have it.
- The loop does not stop at the first match.
How to use this: Click the green flag and watch it call out each matching row before giving the count.
Teacher reveal — the loop goes back to a plain repeat
set [how many v] to (0)
repeat (length of [powers v])
change [n v] by (1)
if <(item (n) of [powers v]) = (want)> then
change [how many v] by (1)
end
end
No found at, no early stop — counting needs every row, so the loop that was carefully stopping early now deliberately does not. Worth naming: “search” and “count” look alike and end differently.
Giving up early
If the deck is already in order, biggest first, you can often stop looking long before the end — because everything below is smaller than what you have just read.
- Sort the powers by hand into 9, 8, 7, 5, 4, 3.
- Search for a power the deck does not have, like 6.
- Stop as soon as the row you are on is smaller than what you want.
How to use this: Click the green flag and compare the two numbers at the end: how many rows it read, and how many there were.
Teacher reveal — the idea behind the idea
repeat until <<<(n) > ((length of [powers v]) - (1))> or <(found at) > (0)>> or <(item ((n) + (1)) of [powers v]) < (want)>>
That condition is getting unreadable, and saying so is part of the lesson — a give up variable set inside the loop is tidier than a three-part test. This is also the door to binary search: if the list is in order, you can do far better than reading from the top. Do not build it; just name it.
Summary 5 min
- Linear search: start at row 1, compare, move down, stop when found.
- A row number of 0 means “not in the list”.
- Best case is one look. Worst case is every row — and proving something is absent is always the worst case.
(item # of () in [names v])is this search with the lid on.- Stopping early is free if the list is in order — and expensive if it is not.
- Algorithm
- A set of steps that solves a kind of problem, not just one problem.
- Linear search
- Looking through a list from one end until you find it.
- Comparison
- One check of one row. What a search costs is counted in these.
- Worst case
- The most work an algorithm can be made to do.
Hand in
Save your deck. Next lesson you put it in order — and watch the strongest cards walk to the top, one swap at a time.