Cambridge O Level Computer Science · Syllabus 2210 · Algorithm Design and Problem-Solving
Linear Search
What is Linear Search?
A standard method of solution that examines the items of a collection one at a time starting at the first, compares each item with the value being searched for, and stops when a match is found or when the end of the collection is reached; it does not require the data to be in any particular order and must report a not-found result when no match exists.
This definition is part of the Algorithm Design and Problem-Solving chapter in Cambridge O Level Computer Science.
Linear Search in context
Topic 7 is about the work that happens before and around writing code. You analyse a problem (identify it, strip away what does not matter, break it into parts, and name the inputs, processes, outputs and storage), you design a solution (structure diagram, flowchart, pseudocode), you code it, and you test it with data you chose on purpose. Along the way you use a small fixed set of standard methods — linear search, bubble sort, totalling, counting, maximum, minimum, average — you protect the input with validation and verification, and you prove behaviour with trace tables and with normal, abnormal, extreme and boundary test data. Nothing in this topic requires you to be fluent in a programming language; it requires you to be exact.
The syllabus limits the standard methods of solution to seven: linear search, bubble sort, totalling, counting, and finding the maximum, minimum and average values. Five of them are “accumulator” methods — a variable is set up before a loop, updated inside it, and used after it. Every one of them has the same three parts, and in every one of them the marks are lost in the same place: the value the accumulator starts with, and whether the update happens on every item or only on some.
A linear search examines the items of a collection one at a time, starting at the first, comparing each with the value being searched for, and stops as soon as a match is found or the end of the collection is reached. It works on data in any order — sorted or not — because it never assumes anything about where the value might be.
Common mistakes with Linear Search
- M11. “A linear search needs the data to be in order.” Correct It works on data in any order. Sorted data is required by a binary search, which is not in this syllabus.
Examiner tips on Linear Search
- Counting comparisons. If the value is at position n, a linear search makes n comparisons. If it is not present at all, it makes as many comparisons as there are items. Those two sentences answer almost every “how many comparisons” question in this topic, and they also explain why a linear search over a large list is slow in the worst case.