A. Programming Concepts and Skills · Arrays and SubprogramsHighest, Lowest and Linear Search
A2.3 A1.6 A4.5About 70 minutes
Learning goals- I can find the highest or lowest value in a list, and its index, without using max() or min().
- I can explain why the tracker should start at the first element, not at 0.
- I can write a linear search that returns the index of a target, or −1 if it is not there.
- I can choose test cases (first, last, middle, missing, repeated, empty) that check a search fully.
Words to know
maximum / minimum
The highest / lowest value in a set of data.
tracker
A variable that remembers the best value (or its index) seen so far while a loop runs.
linear search
Checking the elements of a list one at a time, in order, until the target is found or the list ends.
target (search key)
The value a search is looking for.
sentinel value
A special value that means "nothing" or "stop", such as −1 for "not found" (−1 can never be a real index in a fixed-size array).
test case
One set of inputs plus the output you expect, used to check that a program works.
The warmest day of a cold week
It is February in Thunder Bay and every reading this week is below zero: −14, −9, −22, −6 and −11 °C. Which day was the warmest? You can see it is −6. A program has to find it by looking at every element and remembering the best one so far. The same idea finds the fastest skater, the cheapest flight or the highest mark. In this lesson you will write the maximum/minimum algorithm and the linear search algorithm, the last two array algorithms the curriculum names for this course.
Finding the highest value
- Make a tracker
highest and give it the first element: highest = a[0]. - Visit every element. If the element is greater than
highest, it becomes the new highest. - After the loop,
highest holds the maximum.
For the lowest value, use the same pattern with <.
temps = [-14, -9, -22, -6, -11]
highest = temps[0]
for t in temps:
if t > highest:
highest = t
print("Warmest:", highest)
Output: Warmest: -6.
A classic logic error
Many students start the tracker at 0. With marks or heights that seems to work, because all the values are positive. With Canadian winter temperatures it fails:
temps = [-14, -9, -22, -6, -11]
highest = 0 # BUG: 0 is not one of the temperatures
for t in temps:
if t > highest:
highest = t
print("Warmest:", highest)
Output: Warmest: 0, which is wrong. No element is greater than 0, so the tracker never changes, and the program reports a temperature that is not even in the list. Start at temps[0] and the bug disappears for every possible list.
Where is the best value? Track the index
Often you need to know which element won, not just its value: whose time was fastest, which day was coldest. Track the index instead of the value. Because you start with index 0, the loop can begin at index 1.
names = ["Ana", "Raj", "Kim", "Lou"]
times = [52.4, 49.8, 55.1, 49.8] # seconds for 400 m skate
best_i = 0
for i in range(1, len(times)):
if times[i] < times[best_i]:
best_i = i
print(names[best_i], "was fastest:", times[best_i])
Output: Raj was fastest: 49.8. The list names and the list times are parallel lists: index 1 in both refers to the same skater. Lou also skated 49.8, but < only replaces the best when a time is strictly smaller, so the first one found (Raj) stays.
Built-in shortcuts
Python has max(a) and min(a), and they work well. You will use them in Using Built-in Functions and Modules. Writing the algorithm yourself is still required in this course: it shows you understand it, it works in every language, and it is easy to adapt (for example, to find the index of the maximum, or the longest name).
Linear search
To find a target in a list, a linear search checks the elements one at a time, starting at index 0:
- If an element equals the target, the search stops and reports that index.
- If the loop reaches the end without a match, the target is not in the list. By convention we report −1, a sentinel value, because −1 is never a real position in an array.
The break statement leaves the loop immediately, so no time is wasted after the target is found.
jerseys = [91, 16, 34, 44, 8]
target = int(input("Jersey number? "))
found_at = -1
for i in range(len(jerseys)):
if jerseys[i] == target:
found_at = i
break
if found_at == -1:
print(target, "is not on the team")
else:
print(target, "is at index", found_at)
Two sample runs. Entering 34 prints 34 is at index 2. Entering 50 prints 50 is not on the team.
Python also has the operator in (34 in jerseys gives True or False) and the method jerseys.index(34), which gives the index but raises a ValueError if the target is missing. Both do a linear search for you behind the scenes.
Worked exampleExample 1: Find every match
A die was rolled 6 times: rolls = [3, 6, 1, 6, 2, 6]. Write a program that lists every index where a 6 was rolled, and how many 6s there were.
- We want all matches, so do not
break: the loop must visit every element. - Collect the matching indexes in a new list with
append. The count is the length of that list. - Code:
rolls = [3, 6, 1, 6, 2, 6]
spots = []
for i in range(len(rolls)):
if rolls[i] == 6:
spots.append(i)
print("6 was rolled at indexes", spots)
print("Count:", len(spots))
6 was rolled at indexes [1, 3, 5] and Count: 3
Testing a search: a full range of test cases
A program that works for one input is not proven correct. Choose test cases that cover every kind of situation, write down the expected output first, then run the program and record the actual output.
| Test case | Input (target) | Why it matters | Expected output |
|---|
| Target in the middle | 34 | the normal case | 34 is at index 2 |
| Target first | 91 | lower bound (index 0) | 91 is at index 0 |
| Target last | 8 | upper bound (index 4) | 8 is at index 4 |
| Target missing | 50 | the not-found path | 50 is not on the team |
| Repeated target | list [7, 7], target 7 | which match is reported? | index 0 (the first) |
| Empty list | list [], any target | loop runs zero times | not found, no crash |
Worked exampleExample 2: Spot the bug with a test case
This search "works" for 34 but gives the wrong answer for 91. Find the bug using the test plan.
found_at = -1
for i in range(1, len(jerseys)):
if jerseys[i] == target:
found_at = i
break
- Test "target first" (91): the loop starts at index 1, so index 0 is never checked. Expected index 0; actual −1.
- The "middle" test passed, which is why one test is never enough.
- Fix:
for i in range(len(jerseys)): so the loop starts at 0.
The loop skipped index 0. Boundary test cases (first and last element) catch this kind of off-by-one error.
Just for funWhy did the linear search fail its driving test?
It kept checking every single mirror, one at a time, even after it had found the car behind it. (Someone forgot the break.)
Hands-on activityCard search race
You need: a deck of playing cards (or 20 slips of paper numbered 1 to 20), a timer (a phone works), and a partner.
- Shuffle 10 cards and lay them face down in a row. This is an unsorted array.
- Your partner names a target card. Turn cards over from the left, one at a time, counting your comparisons, until you find it or reach the end. Record the count.
- Repeat 5 times with different targets, including one card that is not in the row. What was the most comparisons you ever needed? Why?
- Now find the highest card the same way: turn cards over from the left, keeping the best card so far in your hand and swapping it when you find a higher one. How many cards did you have to look at? (All 10, every time.)
- Write both algorithms in Python for a list of the same 10 numbers and run your test cases.
What to look for: the student explains that a missing target always costs the full 10 comparisons, and that a maximum always needs every element checked.
Your turn
1Write code that finds the lowest value in prices = [4.99, 2.49, 3.75, 2.99] without using min().
lowest = prices[0]
for p in prices:
if p < lowest:
lowest = p
print(lowest)
It prints 2.49.
2Why should highest start at a[0] instead of 0?
If every element is negative, 0 is higher than all of them, so the answer would be 0, a value not even in the list. a[0] is always a real element.
3Predict the output:
a = [5, 8, 2, 8]
best = 0
for i in range(1, len(a)):
if a[i] > a[best]:
best = i
print(best)
1. Index 1 (8) beats index 0 (5). Index 3 is also 8, but 8 > 8 is false, so best stays 1.
4What should a linear search return when the target is missing, and why that value?
−1. It is a sentinel: −1 can never be a real index, so the caller can tell "not found" apart from any real position.
5What does break do inside a search loop?
It exits the loop immediately, so no more elements are checked after the target is found.
6List four test cases for a search of [12, 40, 7, 25].
Target in the middle (e.g. 40 → 1), first (12 → 0), last (25 → 3), missing (e.g. 99 → −1). An empty list and a repeated target are good extra cases.
More practice: warm-up
1What is the maximum of −3, −8, −1, −12?
2In a list of 50 names, at most how many comparisons does a linear search need?
3Which operator tells you whether a value is in a list?
4What is a sentinel value?
A special value meaning "none" or "stop", such as −1 for not found.
5To find a minimum, which comparison do you use, > or <?
More practice: on your own
1Write code that prints the longest word in words = ["Iqaluit", "Regina", "Charlottetown", "Victoria"].
longest = words[0]
for w in words:
if len(w) > len(longest):
longest = w
print(longest)
It prints Charlottetown (13 letters).
2Write a linear search that prints the index of the last match of target in a (or −1).
found_at = -1
for i in range(len(a)):
if a[i] == target:
found_at = i
print(found_at)
No break: each new match overwrites the old one, so the last match wins. (Or search backwards from the end and break.)
3Predict the output:
a = [4, 9, 1, 9, 3]
lo = a[0]
hi = a[0]
for x in a:
if x < lo:
lo = x
if x > hi:
hi = x
print(hi - lo)
8. hi = 9, lo = 1. This is the range of the data.
4Why does jerseys.index(50) crash when 50 is not in the list? Write a safe version.
index raises ValueError when the value is missing. Safe version:
if 50 in jerseys:
print(jerseys.index(50))
else:
print(-1)
5A search for the coldest day starts with coldest_i = 0 and, inside an index loop, uses if temps[i] <= temps[coldest_i]: coldest_i = i. For [-5, -9, -9], which index does it report, and how is that different from <?
With <=, the tracker also moves on ties, so it reports the last −9, index 2. With < it would report the first, index 1.
Challenge
1Write code that finds the second-highest distinct value in a list of at least two different numbers, in one loop. Test it with [7, 3, 9, 9, 5].
a = [7, 3, 9, 9, 5]
first = max(a[0], a[1])
second = min(a[0], a[1])
for x in a[2:]:
if x > first:
second = first
first = x
elif x > second and x != first:
second = x
print(second)
It prints 7. When a new highest appears, the old highest moves down to second. Ties with the highest are skipped. (This version assumes a[0] and a[1] are different, as in the test list.)
2Suppose a linear search on a list of 1 000 000 names takes 0.05 s in the worst case on a certain laptop. Roughly how long would the worst case take for 4 000 000 names, and why?
About 0.2 s. The worst case checks every element, so the time grows in proportion to the length: 4 times the names, about 4 times the time.
3Design a full test plan (at least 5 cases with expected outputs) for a program that prints the index of the minimum of a list of temperatures.
For example: (1) [-3, -8, -1] → 1 (middle); (2) [-9, -2, 0] → 0 (first); (3) [4, 2, -6] → 2 (last); (4) [5] → 0 (one element); (5) [-4, -4] → 0 with < (tie, first one reported); (6) [] → the program should print a message, not crash (special case). Expected outputs are written before running.
Quiz
1. To find the highest value in a list a, what should the tracker start at?
2. A linear search of 200 elements is looking for a value that is not there. How many comparisons does it make?
3. What does break do in a loop?
4. Which test case would catch a search loop that starts at range(1, len(a))?
5. a = [6, 2, 6]. With if a[i] > a[best]: best = i, starting at best = 0, what is best at the end?
6. Why is −1 a good "not found" result?
Big idea: This completes the array algorithms named in A2.3: finding the highest or lowest value and performing a linear search. A4.5 (validating with a full range of test cases) is introduced with the test plan table.
How to help: Do the card activity together. Then ask, "What test would break this program?" and let your teen try to break their own code with first, last, missing and empty cases.
Common difficulties:
- Starting the max tracker at 0 (fails for negative data) or the min tracker at 0 (fails for positive data). Always start at the first element.
- Forgetting
break, or using it when all matches are wanted. - Printing "not found" inside the loop on every non-match. The not-found decision can only be made after the loop.
- Testing with only one easy input. Encourage the habit of writing expected outputs before running.