AQA 7517 · Paper 1 · 4.3.4

Searching
Algorithms

Linear Search & Binary Search · Section 4.3 Algorithms

WHAT YOU'LL LEARN

Linear search O(n) · Binary search O(log n) · Pseudocode · Comparison

AQA SPEC LINK

4.3.4 — Searching algorithms (linear and binary)

Linear Search

Checks each element one by one from left to right until target found or list exhausted. Works on any list (sorted or unsorted).

FUNCTION linearSearch(arr, target)
  FOR i ← 0 TO LEN(arr) - 1
    IF arr[i] = target THEN
      RETURN i
    ENDIF
  ENDFOR
  RETURN -1  # not found
ENDFUNCTION

Linear Search Trace

Linear Search Example

Array: [4, 7, 2, 9, 1, 5]. Search for 9

Step	Index	Value	Result
1	0	4	4 ≠ 9
2	1	7	7 ≠ 9
3	2	2	2 ≠ 9
4	3	9	9 = 9 FOUND at index 3

Best case: O(1) — item at position 0. Worst case: O(n) — item at end or not found.

Binary Search

Repeatedly halves the search space. Compares target with midpoint. Requires a sorted list. Much faster than linear for large datasets.

FUNCTION binarySearch(arr, target)
  low ← 0
  high ← LEN(arr) - 1
  WHILE low ≤ high DO
    mid ← (low + high) DIV 2
    IF arr[mid] = target THEN RETURN mid
    ELSE IF arr[mid] < target THEN low ← mid + 1
    ELSE high ← mid - 1
    ENDIF
  ENDWHILE
  RETURN -1
ENDFUNCTION

Binary Search Trace

Binary Search Example

Sorted array: [1, 3, 5, 7, 9, 11, 13, 15]. Search for 11

Step	low	high	mid	arr[mid]	Action
1	0	7	3	7	7<11 → low=4
2	4	7	5	11	11=11 FOUND

Only 2 comparisons needed vs up to 6 with linear search. With n=1000: binary needs max 10 comparisons; linear up to 1000.

Complexity Comparison

Linear vs Binary — Complexity

LINEAR SEARCH

Best: O(1)

Average: O(n)

Worst: O(n)

Works on unsorted data

BINARY SEARCH

Best: O(1)

Average: O(log n)

Worst: O(log n)

Requires SORTED data

log n Growth

Why O(log n) Is So Fast

Each comparison halves the search space. 2^10 = 1024, so searching 1024 items takes just 10 steps.

n (list size)	Linear: max steps	Binary: max steps
10	10	4
100	100	7
1,000	1,000	10
1,000,000	1,000,000	20

When to Use

Choosing the Right Algorithm

Use linear search when data is unsorted or list is very small

Use binary search when data is sorted — much more efficient for large datasets

If sorting cost is considered: for one-off search on unsorted data, linear may be faster (no sort overhead)

For repeated searches: sort once, binary search many times = overall faster

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

An array contains the following sorted values: [2, 5, 8, 12, 16, 23, 38, 47, 56, 72]
(a) Perform a binary search for value 23. Show each mid-point value checked. [3]
(b) State the worst-case time complexity of binary search. [1]
(c) Give ONE reason why binary search cannot be used on an unsorted list. [1]

[5 marks]

3 marks

(a) low=0 high=9 mid=4 → 16<23 → low=5; mid=7 → 47>23 → high=6; mid=5 → 23=23 FOUND at index 5

1 mark

(b) O(log n)

1 mark

(c) The midpoint comparison (less than/greater than) only works correctly on sorted data; on unsorted data it cannot determine which half to discard

Summary

Key Points to Remember

Linear search — checks each element; O(n) worst; works on any list

Binary search — halves search space each time; O(log n); needs sorted data

AQA pseudocode: use DIV for integer division: mid ← (low + high) DIV 2

Binary is much faster for large n (log₂(1,000,000) ≈ 20 steps)

Binary requires sorted — if unsorted, must sort first (or use linear)

🎉 Lesson complete — move to the quiz!