Algorithms and programming · GCSE Computer Science
Linear search
GCSE Computer Science linear search: check each item in order, works on unsorted lists, worst case n comparisons, and when it is the right algorithm to name.
Linear search starts at the first item and walks to the end. Unsorted is fine. Worst case is n checks for n items.
The important bits
What you need to know
- 1
Linear search (serial search) compares the target with each item in turn from the start of the list until it finds a match or runs out of items.
- 2
It does not require the data to be sorted. That is the main reason you choose it over binary search on a messy array or a live stream of inputs.
- 3
Best case is one comparison: the target is the first item. Worst case is n comparisons: the target is last, or not present at all.
- 4
If the item is absent you must check every element before you can say “not found”. Do not stop early unless you have extra information (for example a sorted list and you have already passed where it would sit).
- 5
On a sorted list you may stop when the current item is larger than the target, but that is an optimisation — say so if you use it. The standard GCSE linear search does not assume order.
- 6
Time efficiency grows in proportion to n. Doubling the list roughly doubles the worst-case comparisons. Space is tiny: a few variables for the index and the target.
- 7
Use linear search for short lists, unsorted data, or a single one-off lookup where sorting first would cost more than just scanning.
- 8
In pseudocode, watch the index: FOR i ← 0 TO n−1 or FOR i ← 1 TO n depending on the board. Mixing 0-based and 1-based is an instant miss.
Quotations worth analysing
Short evidence. Real method.
“Linear search checks each item in turn until the target is found or the list ends.”
“Each item in turn” is the method mark. “Until found or the list ends” is the termination mark. Missing either loses a two-mark definition.
“Linear search can be used on unsorted data.”
This is the advantage you write against binary search. Do not say linear is “always slower” without naming n or the unsorted precondition.
“Worst case: n comparisons for n items.”
Name the case (worst) and the quantity (comparisons). “It is slow” scores nothing. Absent items are the same n checks as a last-place hit.
Go deeper
Unsorted is a feature, not a flaw
A register of new club members is not in alphabetical order. Linear search still works: start at index 0, compare, step, repeat. Binary search on that list is not “a bit worse”; it is incorrect, because discarding a half assumes order. Exam comparisons want that contrast in one sentence: linear works on unsorted data; binary requires a sorted list. Then add efficiency: for large n, linear’s worst case is n comparisons, which is why you might sort once and then binary-search many times. For a single search of ten names, linear is the honest choice. Do not apologise for it. Choose the algorithm that matches the data you actually have, not the one that sounds more advanced.
Go deeper
Count comparisons, not vibes
Papers ask how many comparisons are needed to find 9 in [4, 1, 9, 2]. Answer: three, because you look at 4, then 1, then 9. To decide 7 is absent you still look at all four. That “not found” case is the one students skip. If two items match the target, standard linear search returns the first index and stops — say so if asked. Efficiency language at GCSE is time (comparisons growing with n) and space (no extra array). You may meet O(n); only write Big O if your specification uses it. Otherwise “time increases in proportion to the number of items” is the mark-scheme English. A 4-mark compare question is linear versus binary: precondition, typical comparisons, and what happens when the item is missing.
See the idea in action
Search for 9 in the unsorted list [4, 1, 9, 2] using linear search. i = 0, list[0] = 4, 4 ≠ 9, continue. i = 1, list[1] = 1, 1 ≠ 9, continue. i = 2, list[2] = 9, 9 = 9, stop. Found at index 2 after 3 comparisons. Now search for 7 in the same list. Compare 4, 1, 9, 2 — none match. After 4 comparisons report not found. Worst case for this list is 4, which equals n. Binary search must not be used here because the list is not sorted; the midpoint 1 would wrongly suggest 7 cannot be to the left, where 4 still sits.
Exam technique
Turn knowledge into marks
If the list is unsorted, name linear search and do not reach for binary. State worst case as n comparisons, including the not-found case.
Common mistakes
Do not give these marks away
- 01
Using binary search on an unsorted list because it “sounds faster”.
- 02
Forgetting that a missing item still needs n comparisons in the standard algorithm.
- 03
Writing “linear search is inefficient” with no reference to n or to the size of the data.
What must be true of the data before linear search will work correctly?
AThe list must already be sorted
BNothing: linear search works on unsorted data
CThe list must have an even number of items
DThe target must appear more than once
Show the answer
Nothing: linear search works on unsorted data. Linear search only needs sequential access. Sorted order is a requirement of binary search, not of linear search. Absence of the target is allowed; you just scan the whole list.
Quick questions
If this is the bit you searched
Does linear search need a sorted list GCSE?
No. It checks items in order from the start. That is why it is used when the data is unsorted or when n is small.
What is the worst case for linear search?
n comparisons for n items, when the target is the last item or is not in the list. Best case is one comparison if it is first.
When is linear search better than binary search?
When the list is unsorted, when it is short, or when you would spend more time sorting than you would save on one lookup.
How do you write linear search in pseudocode?
Loop through each index, compare list[i] with the target, return i if they match, and after the loop return a not-found value. Keep the board’s index start (0 or 1) consistent.