To find 19 in [4, 12, 7, 3, 19, 8] (OCR Exam Reference Language style):
found = false
i = 0
while i < 6 AND found == false
if numbers[i] == target then
found = true
else
i = i + 1
endif
endwhile
Linear search checks the items in order from index 0 until it finds the target:
| Check | i | numbers[i] | numbers[i] == 19? |
|---|---|---|---|
| 1 | 0 | 4 | No |
| 2 | 1 | 12 | No |
| 3 | 2 | 7 | No |
| 4 | 3 | 3 | No |
| 5 | 4 | 19 | Yes, found at index 4 |
The target was found after 5 comparisons, so the loop stops and index 5 is never checked. If the target is not in the list, every item is checked and found stays false.
This study notes covers Linear Search Trace Table within Linear Search for GCSE Computer Science. Revise Linear Search in 3.1 Fundamentals of Algorithms for GCSE Computer Science with 12 exam-style questions and 7 flashcards. This topic shows up very often in GCSE exams, so students should be able to explain it clearly, not just recognise the term. It is section 6 of 9 in this topic. Use this study notes to connect the idea to the wider topic before moving on to questions and flashcards.
Practice questions for Linear Search
How does a linear search work?
Describe how a linear search works on a list of n items. [3 marks]