What is a Linear Search?
A linear search (also called a sequential search) is a searching algorithm that checks each element of a list one by one, from the first to the last, until the target value is found or the end of the list is reached.
Key requirement: The list does NOT need to be sorted — linear search works on any list in any order.
How Linear Search Works — Step by Step
- Start at the first element (index 0)
- Compare the current element with the target value
- If they match → the item has been found; return its position
- If they do not match → move to the next element
- Repeat steps 2–4 until the item is found or the end of the list is reached
- If the end is reached without finding the item → report "not found"
Linear Search — Pseudocode (Edexcel 4CP0)
SET found TO FALSE
SET index TO 0
WHILE index < LENGTH(list) AND found = FALSE DO
IF list[index] = target THEN
SET found TO TRUE
SEND "Found at position " & index TO DISPLAY
ELSE
SET index TO index + 1
END IF
END WHILE
IF found = FALSE THEN
SEND "Not found" TO DISPLAY
END IF
Efficiency — Best, Worst and Average Case
| Case | Description | Comparisons |
|---|
| Best case | Target is the first element in the list | 1 |
| Worst case | Target is the last element or not in the list | n (all elements) |
| Average case | Target is somewhere in the middle | n/2 |
Linear search has O(n) time complexity — as the list doubles in size, the maximum number of comparisons doubles.
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|
| Works on unsorted lists | Slow for large lists — must check every element in the worst case |
| Simple to implement | Less efficient than binary search for sorted lists |
| Works on any data type | Not practical for very large datasets |
📝 Exam Tip: If asked to "trace the linear search algorithm", write the index value and the comparison made at each step. Show clearly when the target is found or when the loop ends without finding it.
⚠️ Common Mistakes
- Saying linear search requires a sorted list — it does NOT (binary search does)
- Stating worst case is n/2 — worst case is n (all elements checked)
- Forgetting the "not found" output when the target is absent