Searching algorithms: linear search and binary search

OCR J277 Paper 2 tests searching algorithms — expect trace table questions (tracing through each pass), code interpretation, and comparison questions. Binary search is more complex but far more efficient.

Linear search

Method

1. Start at the first element.
2. Compare the current element with the target.
3. If found: return the index (position).
4. If not found: move to the next element.
5. If end of list reached without finding the target: return -1 (not found).

Key facts

• No precondition: works on unsorted OR sorted lists.
• Best case: target is the first element → 1 comparison.
• Worst case: target is the last element or not present → n comparisons (n = list length).
• Average case: n/2 comparisons.

Pseudocode

FOR i ← 0 TO LENGTH(list) - 1
    IF list[i] = target THEN
        RETURN i
    END IF
END FOR
RETURN -1

Binary search

Precondition

The list must be sorted before binary search can be used.

Method

1. Find the midpoint of the list: mid = (low + high) ÷ 2 (integer division).
2. Compare the midpoint value with the target.
3. If equal: target found; return the index.
4. If target < midpoint: search the left half (high = mid − 1).
5. If target > midpoint: search the right half (low = mid + 1).
6. Repeat until found or low > high (not found).

Worked example

List: [3, 7, 12, 19, 24, 31, 45] Target: 24

Pass 1: low=0, high=6, mid=3. list[3]=19. 24>19 → left=4. Pass 2: low=4, high=6, mid=5. list[5]=31. 24<31 → right=4. Pass 3: low=4, high=4, mid=4. list[4]=24. Found at index 4. ✓

Key facts

• Precondition: list must be sorted.
• Best case: 1 comparison (target is at the midpoint).
• Worst case: log₂(n) comparisons — e.g. for 1,000 items: max 10 comparisons. For 1,000,000 items: max 20 comparisons.

Comparison

Feature	Linear search	Binary search
Works on unsorted list?	Yes	No (must sort first)
Best case comparisons	1	1
Worst case comparisons	n	log₂(n)
Better for small lists?	Often (no sorting overhead)	No
Better for large sorted lists?	No	Yes — dramatically faster

Common OCR exam mistakes

1. Using binary search on an unsorted list — you MUST state it requires a sorted list.
2. Integer division for midpoint — (0+6)÷2 = 3, not 3.0. The midpoint index is always an integer.
3. Forgetting what to return when target is not found — "return -1" or "target not found".
4. Trace-table errors: updating low/high correctly (low = mid+1 not mid; high = mid-1 not mid).