Community resourceWorksheet

1CP2-CT-4.5 Linear search in one dimension

Part 5 of 7 · 1CP2-CT-4 · Structures, validation and search

The search worksheet, maintaining the three pieces of state a linear search needs and stopping correctly.

Students will:

  • count the comparisons a search makes
  • trace a linear search to its termination
  • explain why both loop conditions are needed
  • write a complete search of their own
  • preserve a correct not-found outcome

Inside: 6 explanation cells, 2 multiple-choice questions, 1 Python task, 1 trace table, 1 fill-in-the-blanks cell and 2 written answers. 14 marks, about 45 minutes.

Series: 1CP2-CT-4 · Structures, validation and search, part 5 of 7.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 17 Aug 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Linear search in one dimension

A linear search checks items one at a time from one end of a structure until it finds the target or reaches the end. It works on sorted and unsorted data.

1. Maintain three pieces of state

Linear search in one dimensiontarget = 22149221831index 0 · compare 1index 1 · compare 2index 2 · foundnot checkednot checkedWorks on sorted or unsorted data · checks one item at a time

A robust search tracks an index, whether the target has been found, and optionally comparisons. It must stop on either outcome: found, or no unchecked items remain.

The number of comparisons depends on the target position. An absent target requires every item to be checked.

Fill in the blanks3 marks
Linear search checks items gap 1 at a time. It works on gap 2 data, and an absent target requires checking gap 3 items.
  • all
  • one
  • only sorted
  • sorted or unsorted
  • two
Multiple choice1 mark

Searching [14, 9, 22, 18, 31] from the left for 18 requires how many comparisons?

  • A1
  • B3
  • C4
  • D5

2. Trace termination

The loop continues while there are unchecked items and the target has not been found. Trace index, found and comparisons.

Trace table5 marks

Trace the linear search and complete the table.

Stop when found becomes True or index reaches the list length.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. values = [7, 4, 9, 2]
  2. target = 9
  3. index = 0
  4. found = False
  5. comparisons = 0
  6. while index < len(values) and found == False:
  7. comparisons = comparisons + 1
  8. if values[index] == target:
  9. found = True
  10. else:
  11. index = index + 1
  12. print(index)
  13. print(comparisons)
Trace table with 8 columns
Rowvaluestargetindexfoundcomparisonsindex < len(values) and found == Falsevalues[index] == targetOutput
1
2
3
4
5
6
7
Written answer2 marks

Explain why both index < len(values) and found == False are needed in the loop condition.

Describe the two ways the search must terminate.

Students type their answer here.

3. Write a complete search

Search names for target using a while loop. Maintain index, found and comparisons. Stop when found or exhausted. Print Found at and the index when found; otherwise print Not found. The supplied target is Cy.

Coding task5 marks
names = ["Ari", "Bo", "Cy", "Dee"]
target = "Cy"
# Complete the linear search and output.

4. Preserve a not-found outcome

When the target is absent, index reaches len(items) and must not be used to read another item. Test found before using the index. Returning or storing -1 is a common sentinel because -1 cannot be a normal positive search index in this design.

Written answer2 marks

A search prints items[index] immediately after its loop, even when the target is absent. Explain the fault and give a safe correction.

Consider the value of index after exhaustion.

Students type their answer here.

Multiple choice1 mark

Which evidence most directly measures work done by this linear search?

  • AThe variable name used for the list
  • BThe number of comparisons made
  • CThe number of comments
  • DWhether the list was created on one line

Route forward

You can trace and construct a one-dimensional linear search with safe found and not-found outcomes. Next you will adapt the same algorithm to search a key field in a list of records.