Home / Reasoning / Search a List: Is It There, and Where?
Reasoning & Coding · Coding
Search a List: Is It There, and Where?
Search a list one item at a time. Use a found flag, remember the position of a match, stop early when you find it, and fix search bugs.
The idea
Your teacher asks, "Is Bo on today's list?" You read down the list one name at a time. If you see Bo, the answer is yes. If you reach the end and never see Bo, the answer is no. That is a search.
A program can search the same way. It uses a variable called a flag that holds true or false. Before the loop, Set found to false, because nothing has been found yet. Inside the loop, If n = target [Set found to true]. After the loop, say found once.
The flag must never be set back to false inside the loop. A common bug adds an else [Set found to false]. Then any item after the match wipes out the answer. Once found is true, it should stay true.
Sometimes you need to know where the match is, not just whether it is there. Count the places with a variable i, and when you find a match, Set pos to i. If the target appears more than once, adding and pos = 0 to the test keeps the first match; leaving it out keeps the last match.
A for-each loop checks every item. If you only need the first match, a Repeat until loop can stop as soon as it finds it. But it also needs a second stop test, or i = length, in case the target is not there at all.
Searching is related to the patterns from the last lessons. A counter tells how many items match. A best-so-far variable finds the biggest. A found flag tells whether there is any match. Choose the pattern that answers your question.
Worked examples
Example 1 · Trace a found flag
Set found to false. For each n in [4, 9, 7, 2] [If n = 7 [Set found to true]]. say found
- Trace table: n | n = 7? | found. Start: found = false.
- 4 no (false) · 9 no (false) · 7 yes (true) · 2 no (still true).
- Nothing sets found back, so it stays true.
It says true.
Example 2 · The else bug
Add else [Set found to false] to Example 1. What happens?
- 4 → false · 9 → false · 7 → true.
- 2 is not 7, so the else runs: found → false.
- The match was wiped out by a later item.
It says false. Remove the else.
Example 3 · Remember where
Set i to 0. Set pos to 0. For each n in [Ali, Bo, Cy, Bo] [Change i by 1; If n = Bo and pos = 0 [Set pos to i]]. say pos
- i goes 1, 2, 3, 4.
- At i = 2, n = Bo and pos = 0, so pos = 2.
- At i = 4, n = Bo but pos is not 0, so pos stays 2.
It says 2, the first Bo.
Example 4 · Stop early, safely
Search [5, 8, 2, 9, 6] for 2 with Repeat until, then search for 4.
- Repeat until item = 2 or i = length: checks 5, 8, 2, then stops after 3 checks.
- For 4: no match, so the or i = length test stops the loop after all 5 items.
- Without the end test, the search for 4 would run past the end.
3 checks for 2; 5 checks for 4, and the end test prevents a runaway loop.
Example 5 · Search a grid
A robot reads a 4-by-3 grid row by row, from the top-left square, and stops at G.
- Row 1: squares 1–4, no G.
- Row 2: S, open, wall, G, so G is square 4 of row 2.
- 4 + 4 = 8 squares read; row 3 is never read.
8 squares.
Common mistakes
Why this fails: Every item after the match resets the flag. Once found is true, it must stay true.
Why this fails: Then a list with no match still says true. Start false and let a match change it.
Why this fails: It restarts on every item, so only the last item matters.
Why this fails: If the target is missing, the loop never stops. Add or i = length.
Why this fails: Then positions start at 0. Count first, then test, so the first item is place 1.
Why this fails: The else bug hides when the match is last. Test with the match first, in the middle, last and missing.
Foundation
Foundation practice
Trace a found flag and say what the program reports.
1. Set found to false. For each n in [4, 9, 7, 2] [If n = 7 [Set found to true]]. say found. What is said?
- false
- 7
- 3
- true
2. Set found to false. For each n in [4, 9, 8, 2] [If n = 7 [Set found to true]]. say found. What is said?
- true
- 0
- 2
- false
3. Why does found start as false before the loop?
- Because false is shorter to type.
- Because the loop needs a number to start.
- Because nothing has been found yet, and only a match should change it.
- Because found must be false at the end.
4. In a search, where should Set found to false go?
- Inside the loop, every time
- Before the loop, once
- After the loop
- Inside the If
5. Set count to 0. For each n in [3, 7, 3, 3, 1] [If n = 3 [Change count by 1]]. say count. How is this different from a found flag?
- It says 3, the number of matches; a found flag would only say true.
- It says true, just like a found flag.
- It says 1, because it stops at the first 3.
- It says 17, the total.
Practice
Practice practice
Remember where the match was and stop when you find it.
6. Set names to [Ali, Bo, Cy, Bo]. Set i to 0. Set pos to 0. For each n in names [Change i by 1; If n = Bo and pos = 0 [Set pos to i]]. say pos. What is said?
- 2
- 4
- 1
- 0
7. Remove 'and pos = 0' from the program above. What is said now?
- 4
- 2
- 3
- 0
8. Set i to 1. Repeat until item i of [5, 8, 2, 9, 6] = 2 [Change i by 1]. say i. What is said?
- 5
- 2
- 3
- 1
9. The same Repeat until loop searches [5, 8, 2, 9, 6] for 4. What problem happens?
- It stops at 2.
- It says true.
- It never finds 4 and runs past the end of the list, so it needs a second stop test: or i = length.
- It finds 4 at the end.
10. Set list to [milk, eggs, bread, jam]. A program checks items one at a time and stops at bread. How many items does it check?
- 4
- 3
- 2
- 1
Think
Think practice
Find the bug in search programs.
11. Set found to false. For each n in [3, 7, 5, 1] [If n = 7 [Set found to true] else [Set found to false]]. say found. It says false, even though 7 is in the list. Why?
- The list is not sorted.
- found should start as true.
- The If should test n > 7.
- The else sets found back to false at every later item that is not 7.
12. The buggy else-program from the last question searches [3, 5, 1, 7] for 7. What does it say, and why is that misleading?
- true, but only because 7 happened to be last.
- false, because the else always wins.
- true, because the bug is fixed.
- It crashes.
13. Set i to 0. Set pos to 0. For each n in [12, 15, 9, 15] [If n = 15 [Set pos to i]; Change i by 1]. say pos. It should report the first 15 at place 2, but it says 3. What are the two bugs?
- The list has two 15s.
- i is changed after the test, so places start at 0, and pos keeps being replaced, so it reports the last 15.
- pos should start at 15.
- The If should use >.
14. Search [red, blue, green] for Blue (capital B). A computer that checks exact letters says false. Why?
- Blue and blue are different text, because capital and small letters do not match exactly.
- green is in the way.
- The list is too short.
- false means it found it.
15. Set found to false. For each n in [2, 4, 6, 8] [If n = 5 [Set found to true]]. say found. What is said, and how many items were checked?
- true; 3
- false; 2
- false; all 4
- 5; 4
Challenge
Challenge practice
Plan searches, count checks and search a grid.
16. A stop-early search looks for 70 in [10, 20, 30, 40, 50, 60, 70]. How many items does it check?
- 1
- 6
- 70
- 7
17. The robot reads the grid row by row, left to right, starting at the top-left square, and stops at G. Counting every square it reads, including G, how many squares does it read?
- 7
- 8
- 12
- 4
18. In [6, 3, 6, 6], what are the first and last places of 6?
- first 1, last 3
- first 1, last 4
- first 2, last 4
- first 3, last 4
19. Write a block program that says yes if any number in nums is bigger than 100, and no otherwise.
20. Why can a search stop early, but a biggest-so-far program cannot?
Answer key
- 1. true
The third item is 7, so found becomes true and nothing sets it back. The program says true or false, not the item (7) or its position (3). - 2. false
No item equals 7, so found keeps its starting value, false. 0 and 2 are not true/false values; 2 is just the last item. - 3. Because nothing has been found yet, and only a match should change it.
Before checking any item, we have not found the target. If found started as true, the program would say true even for a list with no match. - 4. Before the loop, once
It sets the starting value one time. Inside the loop it would wipe out a match; after the loop or inside the If it would come too late or undo the find. - 5. It says 3, the number of matches; a found flag would only say true.
A counter tells how many; a flag tells whether. There are three 3s. The loop does not stop early, and 17 is the total of all items. - 6. 2
i counts the places 1, 2, 3, 4. pos is set at the first Bo (place 2), and the test pos = 0 stops it changing at the second Bo. 4 is the last Bo, 1 is Ali, and 0 would mean not found. - 7. 4
Without the extra test, pos is replaced at every Bo, so it ends with the last one, place 4. This is like a tie with ≥ in the biggest-so-far lesson. - 8. 3
i = 1 is 5, i = 2 is 8, i = 3 is 2, so the loop stops and says 3, the place of the match. It stops early, so it never reaches 5; 2 is the target value, and 1 is only the starting place. - 9. It never finds 4 and runs past the end of the list, so it needs a second stop test: or i = length.
A search that stops only on a match must also stop at the end of the list. Otherwise it keeps looking for a 4 that is not there. - 10. 3
It checks milk, eggs, bread and stops. jam is never checked. Stopping early saves work when the match is near the front. - 11. The else sets found back to false at every later item that is not 7.
After 7, the items 5 and 1 take the else branch, so found is wiped out. Remove the else: once found is true, it should stay true. Sorting and starting true are not the fix. - 12. true, but only because 7 happened to be last.
With 7 at the end, nothing comes after it to reset found, so the bug hides. Test a match in the middle too. - 13. i is changed after the test, so places start at 0, and pos keeps being replaced, so it reports the last 15.
With i changed after the test, the first 15 is at i = 1 and the second at i = 3. Without pos = 0 in the test, pos ends at the last one. Move Change i by 1 to the top and add and pos = 0. - 14. Blue and blue are different text, because capital and small letters do not match exactly.
Many programs compare text letter by letter, so Blue ≠ blue. You can change both to small letters before comparing. - 15. false; all 4
No item is 5, so found stays false. A for-each loop always checks every item, so all 4 are checked. - 16. 7
70 is the last item, so every item is checked. This is the worst case for a front-to-back search. 70 is the value, not a count. - 17. 8
Row 1 has 4 squares (1–4). Row 2 is S, open, wall, G, so G is the 4th square of row 2: 4 + 4 = 8. It stops there, so it never reads row 3. 12 is every square, and 4 is just one row. - 18. first 1, last 4
6 is at places 1, 3 and 4. First is 1, last is 4. A first-match search needs the extra and pos = 0 test; a last-match search does not. - 19. Set big to false. For each n in nums [If n > 100 [Set big to true]]. If big [say yes] else [say no].
Start the flag false before the loop, set it true on a match, never set it back inside the loop, and decide once after the loop. - 20. Once a search finds a match, the answer is known. A biggest-so-far program must see every item, because a bigger one could still be later in the list.
Stopping early is safe only when no later item can change the answer.