- Define and explain Linear Search in your own words
- Use key terms such as linear search accurately
- Apply what you have learned to new examples and questions
- Avoid the common mistakes learners make with this topic
Not all solutions are equal: some find a name in a list of a million in twenty steps, while others need a million. At GCSE you move from writing any working solution to writing good ones. This chapter covers the classic searching and sorting algorithms — and how to measure which is best.
This lesson focuses on Linear Search: find items by checking each one in turn.
Find items by checking each one in turn.
Key ideas
Binary search needs sorted data
Binary search is dramatically faster than linear search — about 20 comparisons for a million items — but it only works if the list is sorted first. Sorting costs time too, so for a one-off search of unsorted data, linear search can still win. The right algorithm depends on the situation, not just the theory.
Worst case is what matters
An algorithm might get lucky and find the target first try, but engineers plan for the worst case — the slowest possible run. Big-O describes this growth: O(n) means doubling the input roughly doubles the time, while O(n²) means doubling the input roughly quadruples it.
Key term — linear search: Checking each item in a list one by one until the target is found. Simple, works on unsorted lists, but slow on large ones.
Use binary search to find 7 in the sorted list [1, 3, 5, 7, 9, 11, 13].
low = 0, high = 6. Middle index = (0 + 6) // 2 = 3. The item at index 3 is 5. 5 is less than 7, so discard the left half: low becomes 4. Middle index = (4 + 6) // 2 = 5. The item at index 5 is 11. 11 is greater than 7, so discard the right half: high becomes 4. Middle index = (4 + 4) // 2 = 4. The item at index 4 is 7. Found — 7 is at index 4, after just 3 comparisons.
Answer: Binary search finds 7 at index 4 in 3 comparisons; linear search would have needed 4.
- Using binary search on an unsorted list Correction: sort the list first, or use linear search — binary search on unsorted data gives wrong answers, not just slow ones.
- Forgetting that list indices start at 0 Correction: in a 7-item list the last index is 6 — off-by-one errors are the classic exam trap, so trace carefully.
Practice
50 — every item must be checked if the target is last or missing.
About 20 — each step halves the remaining items, so a million shrinks to one in roughly 20 halvings.
If the list is unsorted, binary search needs it sorted first — that sorting cost can outweigh the faster search for a one-off lookup.
O(n²) — quadrupling when the input doubles is the signature of quadratic growth.
Quick check
Which of these best defines "linear search"?
True or false: binary search is always the best searching algorithm.
Trace one pass of bubble sort on [5, 3, 8, 1]. What is the list afterwards?
- Linear Search: find items by checking each one in turn.
- Binary search needs sorted data: Binary search is dramatically faster than linear search — about 20 comparisons for a million items — but it only works if the list is sorted first.
- binary search: Repeatedly halving a sorted list to find a target — comparing with the middle item and discarding the half that cannot contain it.
- Watch out for: using binary search on an unsorted list