Tracing a linear search

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

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

2. Which columns would a trace table for a linear search normally include?

A Index, element compared, Found

B Index, swap, temporary

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

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

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

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

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

Definitions

trace table

Fill in the Blanks

Complete each line of code by filling in the missing parts.

Found ← _____ FOR Index ← 1 TO 5 IF List[Index] = Target THEN Found ← TRUE

FOR Index ← 1 TO 5 IF List[_____] = Target THEN Found ← TRUE

FOR Index ← 1 TO 5 Comparisons ← Comparisons _ 1 IF List[Index] = Target THEN Found ← TRUE

IF Found = _____ THEN OUTPUT "Not found" ENDIF

FOR Index ← 1 TO 6 IF List[Index] _ Target THEN Matches ← Matches + 1

Spot the Error

Shade in the letter of the line that contains an 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

Question 2

A Checks ← 1

B FOR Index ← 1 TO 6

C Checks ← Checks + 1

D NEXT Index

E OUTPUT Checks

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

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

Question 5

A Index ← 1

B WHILE Index < 5 DO

C OUTPUT List[Index]

D Index ← Index + 1

E ENDWHILE

Answer Key

Tracing a linear search

Section A: Quick Questions

B — TRUE, because 7 was compared at index 2

A — Index, element compared, Found

B — FALSE

A — 2

A — 6, one for every element

Section B: 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.

Section C: Definitions

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.

Section D: Fill in the Blanks

Found ← FALSE
FOR Index ← 1 TO 5
   IF List[Index] = Target THEN Found ← TRUE

FOR Index ← 1 TO 5
   IF List[Index] = Target THEN
      Found ← TRUE

FOR Index ← 1 TO 5
   Comparisons ← Comparisons + 1
   IF List[Index] = Target THEN Found ← TRUE

IF Found = FALSE THEN
   OUTPUT "Not found"
ENDIF

FOR Index ← 1 TO 6
   IF List[Index] = Target THEN
      Matches ← Matches + 1

Section E: Spot the Error

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.

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.

C — ← is for assignment, not for comparing. An IF needs the comparison operator =, so the line should be IF List[Index] = Target THEN.

D — Position should store the index where the match was found, not the target value. It should be Position ← Index.

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.