Sorting and Searching Algorithms
Algorithm Design and Problem Solving
A examines every item in a list one at a time, in order, until it either finds the target value or runs out of items.
The algorithm is the obvious approach: start at the beginning, check each value, stop when you find a match. It is sometimes called a sequential search.
Step-by-step algorithm
| Step | What it does |
|---|---|
| 1 | Start at the first value in the list |
| 2 | If this value is the target, stop and report found |
| 3 | Otherwise, move to the next value |
| 4 | Repeat steps 2-3 |
| 5 | If the end of the list is reached without finding the target, report not found |
The algorithm works on any list, sorted or unsorted. This is its biggest advantage.

Pseudocode
DECLARE Data : ARRAY[1:10] OF INTEGER
Found ← FALSE
FOR Index ← 1 TO 10
IF Data[Index] = Target
THEN
Found ← TRUE
OUTPUT "Target found at position ", Index
ENDIF
NEXT Index
IF Found = FALSE
THEN
OUTPUT "Target not found"
ENDIF
Exam tip
A linear search is set as a loop with an IF inside it
The papers set the linear search without naming it: a loop over every item with an IF inside comparing each element with the value wanted. When amending an algorithm to search, the credited steps are an input for the value to find before the loop, an IF inside the loop testing whether the array element matches it, the output moved inside that IF, and the loop continuing to the next element otherwise. To stop at the first match use a Found flag: FALSE before the loop, TRUE on a match, and loop while it is FALSE and items remain.
Advantages and disadvantages
| Advantages | Disadvantages |
|---|---|
| Works on any list, sorted or unsorted | Slow on large lists: must check up to every item |
| Simple to write | If the target is near the end (or not present), every item is checked |
| No setup cost (list does not need to be sorted first) |
How long can a linear search take?
For a list of n items:
- Best case: target is the first item; only 1 comparison needed.
- Worst case: target is the last item, or not in the list; n comparisons needed.
- Average case: roughly n/2 comparisons.
For 1 000 items, that is up to 1 000 comparisons. For 1 000 000 items, up to 1 000 000. Linear search does not scale well.
Quick check
4 short questions on this note. See what has stuck, and where to look if something hasn't.