3.10 List traversal and linear searchVisiting every element

Traversing a list means accessing its elements one at a time. A complete traversal visits every element; a partial traversal visits only some, for example stopping once it finds what it needs. FOR EACH item IN aList is the easiest way to traverse: the body runs once per element, in order, with item set to each element. You can also traverse by index, using a counter i from 1 to LENGTH(aList) inside a loop.
?Wait, in FOR EACH t IN temps, is t an index or a value?
The classic traversal algorithms the course names: find the maximum or minimum, and compute the sum or average. Here's the maximum. Start with the first element (a value that's really in the list), then replace it whenever you see something bigger.
1temps ← [71, 68, 77, 74, 77]2best ← temps[1]13FOR EACH t IN temps4{5 IF (t > best)26 {7 best ← t28 }9}10DISPLAY(best)
- line 2 Start with a value that is really in the list
- line 5-7 Keep the biggest seen so far
| t | t > best? | best |
|---|---|---|
| (start) | 71 | |
| 71 | false | 71 |
| 68 | false | 71 |
| 77 | true | 77 |
| 74 | false | 77 |
| 77 | false | 77 |
Why start with temps[1] and not 0? If every value in the list were negative, starting at 0 would leave best at 0, a number that isn't even in the list. That's a logic error that ordinary tests miss. For a sum, though, starting at 0 is exactly right, and the average is the sum divided by LENGTH.
Linear search
A linear search, also called a sequential search, checks each element of a list in order until it finds the value it wants or has checked every element. It works on any list, sorted or not. In the worst case, when the value is last or missing, it checks every element.
1names ← ["Ava", "Ben", "Cruz", "Ben"]2i ← 13found ← 04REPEAT UNTIL ((i > LENGTH(names)) OR (found ≠ 0))15{6 IF (names[i] = "Ben")27 {8 found ← i9 }10 i ← i + 111}12DISPLAY(found)
- line 4 Stop at the end of the list, or once found
- line 6 Check one element at a time, in order
| check | i | stop? | names[i] | found after |
|---|---|---|---|---|
| 1 | 1 | false | "Ava" | 0 |
| 2 | 2 | false | "Ben" | 2 |
| 3 | 3 | true (found ≠ 0) | 2 |
?Wait, why is the stop condition an OR?
I thought about it. Show me
What is displayed?
nums ← [9, 4, 12, 7, 15, 3]
count ← 0
FOR EACH n IN nums
{
IF (n MOD 3 = 0)
{
count ← count + 1
}
}
DISPLAY(count)- The condition n MOD 3 = 0 is true when n is a multiple of 3.
- Go through the list: 9 yes (count 1), 4 no, 12 yes (count 2), 7 no, 15 yes (count 3), 3 yes (count 4).
Why?
3 MOD 3 = 0, so 3 counts as a multiple of itself. - The loop ends after the last element, and count is 4.
Answer: 4
Stuck? Get a hint
- Which numbers in the list divide evenly by 3?
- Don't forget the last one, 3.
- count goes up once for each multiple.
PROCEDURE mystery(nums)
{
m ← nums[1]
FOR EACH v IN nums
{
IF (v < m)
{
m ← v
}
}
RETURN(m)
}- A8
- B3
- C5
- D9
Show the answer
B. It starts at 8 and keeps any smaller value: 3 replaces 8, and nothing after is smaller than 3. It returns the minimum, 3. 5 is the trap: it is the last element, not the smallest.
- ABinary search, about 11 names
- BLinear search, up to 2,000 names
- CBinary search, up to 2,000 names
- DLinear search, about 11 names
Show the answer
B. The list isn't sorted, so binary search won't work. Linear search works on any list, and in the worst case it checks all 2,000.
- Traversal: visit elements one by one. Complete or partial.
- FOR EACH gives values; an index loop gives positions.
- Max/min: start with the first element. Sum: start at 0. Average: sum ÷ LENGTH.
- Linear search checks in order until found or the end; it works on unsorted lists.