SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
AQA 8525 · Section 3.1 · 3.1.3b

Binary
Search

Divide & Conquer · Sorted Lists Only · log₂(n) Efficiency

CSZoneAQA GCSE Computer Science 8525
Learning Objectives

By the end of this lesson you will be able to...

Explain that binary search requires a sorted list
Describe how binary search works by repeatedly halving the search space
Trace a binary search and state how many comparisons are needed
Compare binary search with linear search and choose the best for a given scenario
How It Works

Binary Search — Step by Step

1
The list must be sorted — this is a requirement, not optional
2
Find the middle item of the list: index = (low + high) ÷ 2
3
If the middle item = target → FOUND!
4
If target < middle → search the left half. If target > middle → search the right half
5
Repeat until found or the list is empty (not found)
Worked Example

Searching for 28 in [3, 7, 9, 15, 21, 28, 42]

Pass 1 — middle = index 3 = 15. 28 > 15 → search right half
3
7
9
15
21
28
42
Pass 2 — remaining: [21, 28, 42]. Middle = 28. Match!
21
28 ✓
42
Found in just 2 comparisons!Linear search would need 6 comparisons for the same result.
AQA Pseudocode

Binary Search in AQA Pseudocode

low ← 0
high ← LEN(list) - 1
found ← False
WHILE low <= high AND found = False
  mid ← (low + high) DIV 2
  IF list[mid] = target THEN
    found ← True
    OUTPUT 'Found at ' + mid
  ELSE IF target < list[mid] THEN
    high ← mid - 1
  ELSE
    low ← mid + 1
  ENDIF
ENDWHILE
Pros & Cons

Advantages & Disadvantages

✅ ADVANTAGES
Very efficient — worst case log₂(n) comparisons
Much faster than linear search for large lists
❌ DISADVANTAGES
Requires sorted data — pre-sorting takes extra time
More complex to implement than linear search
⚡ AQA Exam:For 1024 items, binary search needs at most 10 comparisons (log₂1024=10). Linear search needs up to 1024.
Exam Practice

Have a go at this question

AQA-style question
Using the sorted list [2, 5, 8, 12, 16, 23, 38, 56], trace a binary search for the value 23. Show each midpoint checked and state how many comparisons were needed.
4 marks
ANSWER
Pass 1: mid=(0+7)DIV2=3 → list[3]=12, 23>12 → right half [1]. Pass 2: mid=(4+7)DIV2=5 → list[5]=23 → Found! [1]. 2 comparisons total [1]. [Award mark for correct trace method] [1]
Key Takeaways

What to Remember

Must have a sorted list — binary search will not work on unsorted data
Each comparison halves the remaining list — very efficient for large data
Worst case: log₂(n) comparisons — for 1024 items that's just 10!
Use mid = (low + high) DIV 2 (integer division) for the midpoint