AQA A-Level Computer Science (7517)

## Learning Outcomes

- Explain how binary search works on a sorted array or list
- Identify the preconditions needed before binary search can be used correctly
- Trace iterative and recursive binary search step by step
- Write or complete standard binary search pseudocode using lower, upper, and midpoint indices
- Explain why binary search has time complexity **O(log n)** and compare it with linear search
- Recognise common errors, including wrong bound updates and incorrect midpoint handling

## AQA A-Level Computer Science (7517) Syllabus

For the AQA A-Level Computer Science (7517), you are expected to understand binary search as a standard searching algorithm, with a focus on the following syllabus points:

- Know that binary search only works correctly on a **sorted** or **ordered** list/array
- Understand how the algorithm compares the target with the **middle element**
- Identify how the **lower bound** and **upper bound** change after each comparison
- Use **integer division** to calculate the midpoint index
- Explain the two main termination conditions: item found, or search range becomes empty
- Trace or write both standard **iterative** pseudocode and, where required, a **recursive** version
- Explain why binary search has best-case **O(1)** time complexity and average/worst-case **O(log n)**
- Distinguish binary search from linear search in method, preconditions, and efficiency

## Test Your Knowledge

_Attempt these questions before reading this article. If you find some difficult or cannot remember the answers, look more closely at that area during your revision._

1. Why does binary search require the data to be sorted first?
2. If the target is smaller than the middle value, which bound changes?
3. What is the purpose of using integer division when calculating the midpoint?
4. Why is binary search usually faster than linear search on large sorted arrays?
5. What should the algorithm do if the item is not present in the array?

## Introduction

Binary search is one of the most common algorithms in AQA Paper 1. You may be asked to explain it, trace it, complete pseudocode, or state its time complexity. This makes it a high-value topic: it tests algorithmic thinking, array indexing, loop conditions, and Big-O notation in one place.

The core idea is simple. Instead of checking every item one by one, binary search repeatedly checks the middle item of a sorted list and discards half of the remaining values each time. That repeated halving is why the algorithm is much faster than linear search for large ordered data sets.

> **Key Term: binary search**
> A search algorithm for a sorted list or array that checks the middle element and repeatedly discards half of the remaining search space.

### How binary search works

Binary search only works when the data is already in order. That is not a minor detail: it is the condition that makes the whole algorithm valid. If the list is sorted, one comparison with the middle element tells you which half could still contain the target and which half definitely cannot.

For example, suppose we have this sorted array indexed from **0**:

- 0: 5
- 1: 13
- 2: 16
- 3: 19
- 4: 26
- 5: 35
- 6: 37
- 7: 57
- 8: 86
- 9: 90
- 10: 93
- 11: 98

Suppose the target is **90**.

We begin with:

- `first = 0`
- `last = 11`

The midpoint is calculated using integer division:

- `midpoint = (0 + 11) // 2 = 5`

The value at index 5 is **35**.

Now compare:

- Is 35 equal to 90? No.
- Is 35 less than 90? Yes.

Because the list is sorted, everything at index 5 or below is too small to be the answer. So we discard that whole section and move the lower bound:

- `first = midpoint + 1 = 6`

Now the active search range is indices 6 to 11.

New midpoint:

- `midpoint = (6 + 11) // 2 = 8`

Value at index 8 is **86**.

Again:

- Is 86 equal to 90? No.
- Is 86 less than 90? Yes.

So the target must be to the right:

- `first = 9`

Now search range is 9 to 11.

New midpoint:

- `midpoint = (9 + 11) // 2 = 10`

Value at index 10 is **93**.

Now:

- Is 93 equal to 90? No.
- Is 93 less than 90? No.

So the target must be to the left:

- `last = midpoint - 1 = 9`

Now search range is 9 to 9.

New midpoint:

- `midpoint = (9 + 9) // 2 = 9`

Value at index 9 is **90**, so the item is found.

Four values were examined: **35, 86, 93, 90**.

This is much fewer than a linear search might need. In the worst case, linear search on 12 items may check all 12 values. Binary search found the answer in 4 checks because each comparison cut down the range sharply.

> **Key Term: sorted array**
> An array whose elements are stored in order, usually ascending or descending, so relative position gives useful information.
>
> **Key Term: midpoint index**
> The index of the middle element in the current search range, usually calculated as `(lower + upper) // 2`.

The logic of the algorithm depends on a cause-and-effect chain:

1. The list is sorted.
2. So comparing with the middle value gives meaningful information.
3. Therefore one whole half can be ruled out.
4. That leaves a smaller search range.
5. Repeating the process eventually finds the item or proves it is absent.

If the list were unsorted, step 3 would fail. A smaller number might still appear in the right half, or a larger number might still appear in the left half. So binary search would no longer be reliable.

> **Test Tip:** If an exam question asks for one disadvantage of binary search, the safest answer is that the data must already be sorted. Do not just say "it is harder to code" unless the question is clearly about implementation difficulty.

### Iterative binary search pseudocode and tracing

The iterative version is the form most students should be ready to write from memory. It uses a loop and three key index variables: lower bound, upper bound, and midpoint.

A standard version is:

```txt
FUNCTION BinarySearch(data, target)
    lower ← 0
    upper ← LENGTH(data) - 1

    WHILE lower <= upper
        middle ← (lower + upper) DIV 2

        IF data[middle] = target THEN
            RETURN middle
        ELSEIF data[middle] < target THEN
            lower ← middle + 1
        ELSE
            upper ← middle - 1
        ENDIF
    ENDWHILE

    RETURN -1
ENDFUNCTION
```

This version returns the index if found and **-1** if not found. Some questions may use `TRUE/FALSE` instead. Follow the return convention in the question.

> **Key Term: lower bound**
> The index of the first element in the current search range.
>
> **Key Term: upper bound**
> The index of the last element in the current search range.
>
> **Key Term: integer division**
> Division that discards any fractional part, so the result is a whole number index.

Why must the updates be `middle + 1` and `middle - 1`?

Because once `data[middle]` has been checked and did not match, there is no point searching that same index again. If you write `lower ← middle` or `upper ← middle`, you may keep the same midpoint on the next iteration and create an infinite loop.

Here is a worked not-found example using the same array and target **36**.

Initial values:

- `lower = 0`
- `upper = 11`

Step 1:

- `middle = (0 + 11) // 2 = 5`
- `data[5] = 35`
- 35 < 36, so `lower = 6`

Step 2:

- `middle = (6 + 11) // 2 = 8`
- `data[8] = 86`
- 86 > 36, so `upper = 7`

Step 3:

- `middle = (6 + 7) // 2 = 6`
- `data[6] = 37`
- 37 > 36, so `upper = 5`

Now `lower = 6` and `upper = 5`.

Since `lower > upper`, the search range is empty. The item is not in the array, so return **-1**.

Students often understand "found" termination but forget the "empty range" termination. Both matter. A binary search must stop either because the item was found or because there are no candidate elements left.

> **Test Tip:** In trace questions, write down the values of `lower`, `upper`, `middle`, and `data[middle]` after each pass. This prevents errors when the bounds change quickly.

Common student errors in iterative binary search:

- Forgetting that the list must be sorted
- Using normal division instead of integer division
- Updating to `lower ← middle` or `upper ← middle` instead of excluding the tested midpoint
- Writing the loop condition incorrectly, such as `lower < upper` when the final single-item check still needs to happen
- Returning the value instead of the index when the question expects the index

A subtle point is the midpoint choice when the range length is even. If you use integer division on `(lower + upper) // 2`, the algorithm usually selects the left-middle index. That is fine, as long as the rest of the logic matches.

### Recursive binary search

Binary search can also be written recursively. Recursion suits the idea of repeatedly solving the same smaller problem: search either the left half or the right half.

A standard recursive version is:

```txt
FUNCTION BinarySearchRecursive(data, target, lower, upper)
    IF upper < lower THEN
        RETURN -1
    ENDIF

    middle ← (lower + upper) DIV 2

    IF data[middle] = target THEN
        RETURN middle
    ELSEIF data[middle] < target THEN
        RETURN BinarySearchRecursive(data, target, middle + 1, upper)
    ELSE
        RETURN BinarySearchRecursive(data, target, lower, middle - 1)
    ENDIF
ENDFUNCTION
```

The base cases are what stop the recursion:

- `data[middle] = target`, so return the answer
- `upper < lower`, so the search range is empty and the item is not found
  > **Key Term: recursive binary search**
  > A version of binary search in which the function calls itself on either the left half or the right half of the current search range.

The recursive and iterative versions do the same logical work. The difference is how the repetition is expressed:

- **Iterative**: uses a loop and updates variables directly
- **Recursive**: uses repeated function calls with new bounds

For AQA, you should be able to read either style and trace it. You do not need to claim that one is the only correct version.

There is also a memory difference:

- Iterative binary search has space complexity **O(1)** because it uses a fixed number of variables
- Recursive binary search has space complexity about **O(log n)** because each recursive call uses stack space

That space point is less commonly tested than time complexity, but it shows good understanding.

One more exam distinction: array/list binary search is not the same as binary tree search. They use similar left/right decision-making, but one works on indices in ordered data, while the other moves through nodes and child pointers.

### Time complexity, efficiency, and comparison with linear search

The main reason binary search matters is efficiency. Each comparison halves the remaining search area.

If there are `n` items:

- after 1 comparison, about `n/2` remain
- after 2 comparisons, about `n/4` remain
- after 3 comparisons, about `n/8` remain

After `i` comparisons, about `n / 2^i` items remain.

To reduce the search range to 1 item:

- `n / 2^i = 1`
- so `n = 2^i`
- therefore `i = log2 n`

That is why binary search has time complexity **O(log n)**.

> **Key Term: time complexity**
> A measure of how the running time of an algorithm changes as the input size increases.
>
> **Key Term: O(log n)**
> Logarithmic time complexity, where the number of steps grows slowly because the problem size is repeatedly halved.

Best case is different. If the middle element is the target immediately, only one comparison is needed, so the best-case time complexity is **O(1)**.

Now compare this with linear search:

- **Linear search** checks one element at a time
- Worst case: **O(n)**
- Average case: **O(n)**
- Binary search:
  - Best case: **O(1)**
  - Average case: **O(log n)**
  - Worst case: **O(log n)**

A worked comparison helps. Suppose you search one million sorted items.

For linear search:

- worst case = 1,000,000 checks

For binary search:

- number of checks is about `log2(1,000,000)`
- since `2^20 = 1,048,576`, this is about **20** comparisons

That difference is huge. Around 20 checks versus up to 1,000,000.

However, you must evaluate properly. Binary search is not always the automatic best choice.

On the one hand, it is far faster on large sorted arrays.

On the other hand, if the data is unsorted, you cannot use binary search directly. If you first need to sort the data, that sorting step adds extra cost. For a very small list or a one-off search, a linear search may be simpler and perfectly acceptable.

Students often write "binary search is always better." That is too absolute. The better answer is:

- binary search is usually better for **large, sorted** data
- linear search may be more suitable for **small** or **unsorted** data

A final detail: standard binary search only guarantees finding **an occurrence** of a value. If duplicates exist, it does not necessarily return the first or last duplicate unless the algorithm is specially changed.

> **Test Tip:** If a question asks why binary search is **O(log n)**, do not just state "because it is fast". Say that each comparison halves the remaining search interval, producing logarithmic growth in the number of comparisons.

## Key Point Checklist

_This article has covered the following key knowledge points:_

- Binary search is used to search a **sorted** list or array
- The algorithm compares the target with the **middle element**
- If the target is smaller than the middle value, the upper half is discarded
- If the target is larger than the middle value, the lower half is discarded
- The midpoint is usually calculated with **integer division**
- Standard iterative binary search uses `lower`, `upper`, and `middle` indices
- The algorithm stops when the item is found or when `lower > upper`
- A common return convention is index if found and **-1** if not found
- Best-case time complexity is **O(1)**
- Average-case and worst-case time complexity are **O(log n)**
- Binary search is generally more efficient than linear search on large sorted lists
- Recursive binary search uses the same logic as iterative binary search but with repeated function calls

## Key Terms and Concepts

- binary search
- sorted array
- midpoint index
- lower bound
- upper bound
- integer division
- recursive binary search
- time complexity
- O(log n)


Algorithms - Binary search