AQA A-Level Computer Science (7517)

## Learning Outcomes

- Explain how a linear search works step by step on a list or array
- Write and trace pseudocode for a linear search using indices, a loop, and a not-found return value
- Distinguish between index, position, value, and first occurrence
- State and justify the best-case, average-case, and worst-case time complexity of linear search
- Explain why linear search is suitable for unsorted data
- Compare linear search with binary search and choose the more suitable method for a given situation

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

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

- Know that a **linear search** checks items one by one from the start of a list until the target is found or the list ends
- Identify that linear search works on both sorted and unsorted data, but does not make use of sorted order
- Understand how to write or complete pseudocode for a linear search over an array or list
- Explain what the algorithm should return when the target is found and when it is not found
- Understand that a standard linear search usually returns the first occurrence when duplicate values exist
- State the best-case, average-case, and worst-case time complexity of linear search using **Big-O notation**
- Compare linear search with binary search, especially the trade-off between simplicity 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. How does a linear search find a target value in a list?
2. Why can a linear search be used on unsorted data?
3. What should a linear search return if the target is not present?
4. What are the best-case, average-case, and worst-case time complexities of linear search?
5. If a list contains duplicate target values, which one does a standard linear search usually return?

## Introduction

Searching is one of the most common jobs in computing. A program may need to find a customer ID in an array, a username in a list, or a score in memory. The method used to search matters because different algorithms take very different amounts of time as the data set grows.

Linear search is one of the simplest algorithms in the AQA specification. That simplicity makes it easy to trace in an exam, but students often lose marks by mixing up the index and the value, forgetting the not-found case, or giving incomplete complexity answers. You need to know not just what the algorithm does, but how it works line by line and why its time complexity is **O(n)** in the average and worst case.

> **Key Term: linear search**
> A search algorithm that checks each item in a list or array one at a time from the start until the target is found or the end of the data is reached.

### How linear search works

The idea is simple: start at the first item, compare it with the target value, and keep moving forward until either a match is found or there are no items left.

Suppose the array is:

`[18, 5, 42, 9, 31]`

and the target is `42`.

A linear search makes these comparisons in order:

1. Compare `18` with `42` → not equal
2. Compare `5` with `42` → not equal
3. Compare `42` with `42` → equal, so stop

The search returns the index of the match if the question asks for the index. With zero-based indexing, `42` is at index `2`.

This method works whether the data is sorted or unsorted. That is one of its main strengths. If the list were `[42, 5, 31, 9, 18]`, linear search still works. If the list were `[5, 9, 18, 31, 42]`, it also works. The algorithm does not depend on order.

> **Key Term: target value**
> The item the algorithm is trying to find in the list or array.

A standard linear search usually stops as soon as it finds the first match. This matters for two reasons. First, it saves time because there is no point checking later items once the required answer has already been found. Second, if duplicates exist, stopping immediately returns the **first occurrence**.

For example, in:

`[7, 4, 9, 4, 2]`

searching for `4` from left to right should return index `1`, not index `3`, if the algorithm stops at the first match.

> **Key Term: first occurrence**
> The earliest position in the list where the target value appears.

A common exam mistake is to keep scanning after a match when the question only asks whether the item exists or asks for its position. That version is less efficient and may return the wrong match if duplicates are present.

> **Test Tip:** Read the wording carefully. If the question asks for the index or position of the item, the expected algorithm usually stops at the first match and returns immediately.

### Writing and tracing linear search pseudocode

You need to be comfortable with more than one valid style of pseudocode. An examiner may show a version using a `FOR` loop, a `WHILE` loop, a `found` flag, or an immediate `RETURN`. All are acceptable if the logic is correct.

A clear AQA-style version is:

```txt
FUNCTION linearSearch(data, target)
    FOR i ← 0 TO LENGTH(data) - 1
        IF data[i] = target THEN
            RETURN i
        ENDIF
    ENDFOR
    RETURN -1
ENDFUNCTION
```

This version does three key things:

- starts at index `0`
- checks each element once
- returns `-1` if the target is not found

The `-1` is a common **sentinel value** because valid indices in a zero-based array cannot be negative.

> **Key Term: sentinel value**
> A special value used to show a particular condition, such as `-1` to mean “not found”.

Here is the same logic using a `WHILE` loop and a Boolean flag:

```txt
numberToFind ← USERINPUT
i ← 0
dataFound ← False

WHILE (i < LENGTH(dataSeq)) AND (dataFound = False)
    IF dataSeq[i] = numberToFind THEN
        dataFound ← True
    ELSE
        i ← i + 1
    ENDIF
ENDWHILE

IF dataFound = True THEN
    OUTPUT "Data found in position: " + i
ELSE
    OUTPUT "Data not found"
ENDIF
```

This version is useful for tracing because you can watch `i` and `dataFound` change after each pass.

Now trace an example.

Array: `[14, 22, 8, 35]`  
Target: `35`

| Step  |   i | dataSeq[i] | Comparison with 35 | dataFound |
| ----- | --: | ---------: | ------------------ | --------- |
| Start |   0 |         14 | 14 = 35? No        | False     |
| Next  |   1 |         22 | 22 = 35? No        | False     |
| Next  |   2 |          8 | 8 = 35? No         | False     |
| Next  |   3 |         35 | 35 = 35? Yes       | True      |

Output: position/index `3` if zero-based indexing is being used.

Now trace an unsuccessful search.

Array: `[14, 22, 8, 35]`  
Target: `10`

The algorithm compares all four items, finds no match, reaches the end of the list, and returns `-1` or “not found”.

Why does the unsuccessful case matter so much? Because many students write only the “found” part and forget what happens if the loop finishes with no match. That makes the algorithm incomplete.

Common student errors include:

- using `FOR i ← 0 TO LENGTH(data)` instead of `LENGTH(data) - 1`, which causes an out-of-bounds access
- returning the value instead of the index when the question asks for position
- forgetting the not-found return
- mixing zero-based index with one-based human position

For example, if the array is `[11, 25, 30]`, then `30` is:

- at **index 2** in zero-based storage
- in **position 3** if using human counting

These are not the same.

> **Test Tip:** If the question says “position”, check whether the example or pseudocode uses zero-based indexing. Do not assume index and position mean the same thing.

### Time complexity of linear search

In exams, you must be able to state and justify the complexity, not just memorise it.

> **Key Term: Big-O notation**
> A way of expressing how the running time of an algorithm grows as the size of the input, usually written as `n`, increases.

Let `n` be the number of items in the list.

Each step of a linear search makes one comparison between the current item and the target. So the running time depends on how many comparisons are needed before the algorithm stops.

#### Best case

The best case happens when the target is the first item.

Example:

Array: `[50, 21, 9, 14]`  
Target: `50`

Only one comparison is needed, so the time complexity is **O(1)**.

This does not mean linear search is always constant time. It means there is one special case where the running time does not depend on `n`.

#### Worst case

The worst case happens when:

- the target is the last item, or
- the target is not in the list at all

In both cases, the algorithm may need to check every item.

Example:

Array length = `n`

Comparisons needed in worst case = `n`

So the worst-case time complexity is **O(n)**.

This is the complexity most often quoted when comparing search algorithms, because Big-O usually refers to the upper bound or worst-case growth.

#### Average case

If the target is equally likely to be anywhere in a successful search, the average number of comparisons is:

`(1 + 2 + 3 + ... + n) / n`

The total of `1 + 2 + 3 + ... + n` is:

`n(n + 1) / 2`

So the average number of comparisons is:

`[n(n + 1) / 2] / n`

`= (n + 1) / 2`

Worked example with `n = 9`:

Average comparisons  
`= (9 + 1) / 2`  
`= 10 / 2`  
`= 5`

So on average, about 5 comparisons are needed in a successful search of 9 equally likely positions.

In Big-O notation, constants are ignored, so `(n + 1) / 2` becomes **O(n)**.

For an unsuccessful search in an unordered list, the algorithm must check all `n` items, so that is also **O(n)**.

Here is the summary:

| Case                           |       Comparisons | Time complexity |
| ------------------------------ | ----------------: | --------------- |
| Best                           |                 1 | O(1)            |
| Average successful             | about (n + 1) / 2 | O(n)            |
| Worst                          |                 n | O(n)            |
| Unsuccessful in unordered list |                 n | O(n)            |

Students often ask why average case is not `O(n/2)`. The reason is that Big-O ignores constant factors. Since `n/2` still grows in direct proportion to `n`, it is written as **O(n)**.

### When linear search is suitable, and how it compares with binary search

Linear search is often called inefficient, but that does not mean it is never useful. The right algorithm depends on the data and the task.

Linear search is suitable when:

- the data is **unsorted**
- the list is **small**
- you only need to perform **one or a few searches**
- simplicity matters more than speed

If the list is unsorted, binary search cannot be used directly. You would have to sort the data first. Sorting usually takes more time than one simple linear search, especially if you only need to search once.

For example, if you have an unsorted array of 20 values and need to find one target once, a linear search is a sensible choice. Sorting first would add extra work for no benefit.

Binary search becomes more suitable when:

- the data is already **sorted**
- the data set is **large**
- many repeated searches will be carried out

This is because binary search cuts the remaining search area roughly in half each time, giving **O(log n)** time complexity. Linear search does not reduce the search space in that way; it just moves one step at a time.

Side-by-side comparison:

| Feature                    | Linear search | Binary search                   |
| -------------------------- | ------------- | ------------------------------- |
| Requires sorted data?      | No            | Yes                             |
| Checks items               | One by one    | Middle item, then half the list |
| Works on unsorted data?    | Yes           | No                              |
| Worst-case time complexity | O(n)          | O(log n)                        |
| Easier to write and trace? | Yes           | Usually no                      |

A very common mistake is saying linear search is only for unsorted data. That is wrong. It can search sorted data too. The correct point is that it does **not benefit from** sorted order.

Another common mistake is choosing binary search automatically because it is faster. It is only faster when its condition is met: the data must be sorted.

> **Key Term: sequential search**
> Another name for linear search, meaning the data is checked in sequence from the start.

If an exam question asks which algorithm should be used, justify your answer with the data structure and data order. Saying “binary search is faster” is too vague. A stronger answer is: “The list is unsorted, so binary search cannot be applied without sorting first. A linear search is therefore the suitable method.”

## Key Point Checklist

_This article has covered the following key knowledge points:_

- A linear search checks each item in a list or array from the start until the target is found or the end is reached
- Linear search works on both sorted and unsorted data
- A standard linear search usually stops at the first match and returns the first occurrence
- If the item is not found, the algorithm should return a sentinel value such as `-1` or output “not found”
- In zero-based indexing, the first item is at index `0`
- Best-case time complexity is **O(1)** because the target may be the first item
- Worst-case time complexity is **O(n)** because every item may need to be checked
- Average-case time complexity is **O(n)**, with about `(n + 1) / 2` comparisons for a successful search with equally likely positions
- An unsuccessful search in an unordered list requires `n` comparisons
- Common errors include off-by-one loop bounds, confusing index with value, and forgetting the not-found case
- Linear search is simple and useful for small or unsorted lists
- Binary search is usually faster on large sorted lists, but it requires the data to be ordered

## Key Terms and Concepts

- linear search
- target value
- first occurrence
- sentinel value
- Big-O notation
- sequential search


Algorithms - Linear search