← IGCSE Computer Science Paper 2

Tracing a linear search

A table that records the index, the element compared and the Found flag on each pass of a linear search, so you can follow it step by step.

Part of: IGCSE Computer Science 0478 — 7d Standard Methods of Solution — Module 38, WA Computer Science ATAR Year 11 — Standard Algorithms — Module 22

Understanding Tracing a linear search in IGCSE Computer Science Paper 2

What it does: The IF compares the element with the target, so Found is set to TRUE only on the matching row. Every other row leaves it unchanged. This line runs once per element compared. The final value in the trace table is the number of comparisons made. Index 1 holds 4 and index 2 holds 7, so the match happens on the second pass and Found becomes TRUE. It compares 2, then 5, and then stops. That is 2 comparisons. A search that does not stop early would make all 4. A linear search checks from the start, so the first 6 at index 1 is met before the duplicate at index 3.

Common mistakes: The Found flag must start as FALSE. If it starts as TRUE, the first row of the trace table already shows TRUE and the search cannot tell when the target is missing. It should be Found ← FALSE. The comparison counter must start at 0 because no comparisons have been made yet. Starting at 1 makes the final count one too high. It should be Checks ← 0.

Class: _____________________  ·  Name: _____________________  ·  Date: _________

Free printable worksheet with full answer key — or add this module to a class and your students practise it interactively.

🖨 Print worksheet + answer key Add Tracing a linear search to a class →

This module's key terms are also in a printable crossword (Modules 296–306) and word search (Modules 296–316).

Take this worksheet further — free with Cloodit

Each concept is reinforced from every angle — learned, then applied, then tested.

Learning
Duo
A linear search looks for 7 in the array [4, 7, 9, 7]. After the pass for index 2, what does the trace table show for Found?
FALSE, because 7 has not been checked yetTRUE, because 7 was compared at index 2
Matches
Data has indexes 1 to 5. First row: 0 | Data[0] | FALSE
↓
The trace table starts at index 0, but Cambridge arrays usually start at index 1. The first row should be 1 | Data[1] | FALSE.
Applying
Meanings
Term
trace table
Meaning
A table that records the index, the element compared and the Found flag on each pass of a linear search, so you can follow it step by step.
Practice
Found ← FALSE
Testing
Gaps
Found ←
Check Answer
Spots
1Found ← TRUE
2FOR Index ← 1 TO 5

Cloodit turns curriculum-aligned coding content into journeys students work through one biome at a time.

The 'Cosmic Dragon' badge — Orbit Master, one of Cloodit's 106 collectible badges
Students earn collectable badges

Over 100 of them, across seven natural biomes.

Study Buddy
Students build a real study resource

Turns their work into revision material ready for Flash Cards and Exam study.

Diamond Dash — one of Cloodit's live, competitive Sprint games
Students lock in with Sprints

Live, competitive practice for the start of the lesson or a teacher-led lesson finisher.

A Cloodit certificate of achievement, ready to personalise and print
Custom printable certificates

Honour your top performers, or encourage a student who's trying hard — ready to print in seconds.

Add to class →

Quick Questions

1. A linear search looks for 7 in the array [4, 7, 9, 7]. After the pass for index 2, what does the trace table show for Found?
A. FALSE, because 7 has not been checked yet
B. TRUE, because 7 was compared at index 2 ✓
Index 1 holds 4 and index 2 holds 7, so the match happens on the second pass and Found becomes TRUE.
2. Which columns would a trace table for a linear search normally include?
A. Index, element compared, Found ✓
B. Index, swap, temporary
A linear search trace records the index, the element being compared and the Found flag. Swap and temporary belong to bubble sort.
3. The target 12 is not in the array [3, 8, 5]. What is the final value of Found in the trace table?
A. TRUE
B. FALSE ✓
Found starts as FALSE and only changes to TRUE if a match is made. With no match it stays FALSE on every row.
4. A search for 5 in [2, 5, 8, 1] stops as soon as it finds the target. How many comparisons are made?
A. 2 ✓
B. 4
It compares 2, then 5, and then stops. That is 2 comparisons. A search that does not stop early would make all 4.
5. The target 9 is not in an array of 6 elements. How many comparisons does a linear search make?
A. 6, one for every element ✓
B. 0, because the target is missing
To prove the target is absent, every element must be compared, so there are 6 comparisons and Found stays FALSE.

Match the Pairs

Index | Data[Index] | Found → The column headings of a trace table for a linear search: the index, the element compared and the Found flag.
Target = 9, row: 2 | 9 | TRUE → On the pass at index 2 the element 9 matched the target, so Found became TRUE.
Found changes to TRUE in the trace table only on the row where the element equals the target → IF Data[Index] = Target THEN Found ← TRUE ENDIF
To count comparisons, add 1 on every pass, so the Comparisons column goes up by one on each row → Comparisons ← Comparisons + 1
Data has indexes 1 to 5. First row: 0 | Data[0] | FALSE → The trace table starts at index 0, but Cambridge arrays usually start at index 1. The first row should be 1 | Data[1] | FALSE.
Target = 8. Row: 3 | 8 | FALSE → The element compared (8) equals the target, so Found should be TRUE on this row, not FALSE.

Key Term

trace table
A table that records the index, the element compared and the Found flag on each pass of a linear search, so you can follow it step by step.

Fill in the Blanks

1. Found ← FALSE FOR Index ← 1 TO 5 IF List[Index] = Target THEN Found ← TRUE
Hint: Type the Boolean value the Found flag holds in the first row of the trace table, before any element is compared.
2. FOR Index ← 1 TO 5 IF List[Index] = Target THEN Found ← TRUE
Hint: Type the loop variable that picks which array element is compared with the target on each pass.
3. FOR Index ← 1 TO 5 Comparisons ← Comparisons + 1 IF List[Index] = Target THEN Found ← TRUE
Hint: Type the arithmetic operator that raises the comparison count by one on every pass.
4. IF Found = FALSE THEN OUTPUT "Not found" ENDIF
Hint: Type the Boolean value the flag still has at the end of the trace when the target was never in the list.
5. FOR Index ← 1 TO 6 IF List[Index] = Target THEN Matches ← Matches + 1
Hint: Type the comparison operator that tests whether the element equals the target, so every duplicate is counted.

Spot the Error

Question 1
A Found ← TRUE
B FOR Index ← 1 TO 5
C IF List[Index] = Target THEN
D Found ← TRUE
E ENDIF
F NEXT Index
Line A — The Found flag must start as FALSE. If it starts as TRUE, the first row of the trace table already shows TRUE and the search cannot tell when the target is missing. It should be Found ← FALSE.
Question 2
A Checks ← 1
B FOR Index ← 1 TO 6
C Checks ← Checks + 1
D NEXT Index
E OUTPUT Checks
Line A — The comparison counter must start at 0 because no comparisons have been made yet. Starting at 1 makes the final count one too high. It should be Checks ← 0.
Question 3
A FOR Index ← 1 TO 5
B Checks ← Checks + 1
C IF List[Index] ← Target THEN
D Found ← TRUE
E ENDIF
F NEXT Index
Line C — ← is for assignment, not for comparing. An IF needs the comparison operator =, so the line should be IF List[Index] = Target THEN.
Question 4
A Position ← 0
B FOR Index ← 1 TO 5
C IF List[Index] = Target THEN
D Position ← Target
E ENDIF
F NEXT Index
Line D — Position should store the index where the match was found, not the target value. It should be Position ← Index.
Question 5
A Index ← 1
B WHILE Index < 5 DO
C OUTPUT List[Index]
D Index ← Index + 1
E ENDWHILE
Line B — The list has 5 elements, so Index must reach 5. Using < 5 stops at 4 and never checks the last element. It should be WHILE Index <= 5 DO.

Student with a class code? Join your class →