A linear search looks through a list from the first item onwards until it finds the target or runs out of items. In an exam you are usually given the algorithm and some data, and asked to complete a trace table and state the result.
This lesson belongs to searching, sorting and files. It relies on the loop and array ideas from repetition and arrays.
How do I trace an algorithm step by step?
A trace table has one column for each variable and one row for each time the values change. You act as the computer: read one line, update only what that line changes, and write the new values.
Three habits make it reliable:
- List every variable that appears in the code, including flags such as
Found. - Evaluate the loop condition each time, before you enter the body.
- Copy unchanged values down so each row shows the full state.
Worked example
A fictional shop stores six product codes in an array. The array has positions 1 to 6.
| Position | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Codes | 14 | 9 | 27 | 9 | 31 | 5 |
Found ← FALSE
Index ← 1
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE THEN
OUTPUT "Found at position ", Index
ELSE
OUTPUT "Not found"
ENDIFTrace with Target = 27.
| Step | Index | Codes[Index] | Codes[Index] = Target? | Found |
|---|---|---|---|---|
| Start | 1 | FALSE | ||
| Pass 1 | 1 | 14 | No | FALSE |
| Pass 2 | 2 | 9 | No | FALSE |
| Pass 3 | 3 | 27 | Yes | TRUE |
After pass 3, Found is TRUE, so the condition fails and the loop ends. The output is Found at position 3, after three comparisons.
Trace with Target = 8. No code equals 8, so the loop runs for Index = 1, 2, 3, 4, 5, 6 with six failed comparisons. After the sixth, Index becomes 7. The condition Index <= 6 is now false, so the loop ends with Found still FALSE. The output is Not found, and the search made six comparisons.
The mistake to watch for
Here is a version that moves the index even after a match:
WHILE Index <= 6 AND Found = FALSE
IF Codes[Index] = Target THEN
Found ← TRUE
ENDIF
Index ← Index + 1
ENDWHILEWith Target = 27, the match happens at Index = 3, but the increment line still runs, so Index becomes 4 before the loop ends. The output would say position 4, and Codes[4] is 9, not 27.
The correction is to put Index ← Index + 1 in the ELSE branch so it only runs when the item did not match. When you trace, ask on every row: “which line changed this variable, and was it allowed to run?”
Check yourself
Use the same array and algorithm.
1. Target = 31. What is output and how many comparisons are made?
Show answer
Index goes 1, 2, 3, 4, 5. Codes[5] = 31 matches on the fifth comparison. Output: Found at position 5, five comparisons.
2. Target = 9. Which position is reported, and why is position 4 never reported?
Show answer
Codes[2] = 9 matches on the second comparison, so Found becomes TRUE and the loop ends. Output: Found at position 2. Position 4 also holds 9 but the loop stopped before reaching it.
3. Target = 5. How many comparisons are made, and is this the best case or the worst case for a found target?
Show answer
The 5 is last, at position 6, so six comparisons. That is the worst case for a target that is present, because every item is checked.
Where this leads next
Once a trace feels steady, try explaining one pass of a sort, where values move instead of just being read. The restricted pseudocode trace trainer lets you step through an algorithm like this one and compare your table with the machine’s.
Some students can read the code but lose marks because a trace row quietly skips a change. That is the kind of habit our teachers look for in online one-to-one Computer Science tuition.