AQA 8525 · Section 3.1 · 3.1.3a

Linear
Search

Sequential searching · Best & Worst Case · AQA Pseudocode

CSZoneAQA GCSE Computer Science 8525

Learning Objectives

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

Describe how linear search works step by step

Trace a linear search algorithm using a trace table

State the best and worst case number of comparisons

List the advantages and disadvantages of linear search

How It Works

Linear Search — Step by Step

1

Start at the first item in the list (index 0)

2

Compare the current item with the target value

3

If it matches → return the position (found!) and stop

4

If it doesn't match → move to the next item and repeat

5

If you reach the end of the list without finding it → report not found

Visualisation

Searching for 42 in this list...

List: [7, 15, 3, 42, 9, 28]

7

15

3

42 ✓

9

28

Check 1: 7 ≠ 42 → move on

Check 2: 15 ≠ 42 → move on

Check 3: 3 ≠ 42 → move on

Check 4: 42 = 42 → FOUND at index 3! — 4 comparisons needed

AQA Pseudocode

Linear Search in AQA Pseudocode

found ← False
i ← 0
WHILE i < LEN(list) AND found = False
  IF list[i] = target THEN
    found ← True
    OUTPUT 'Found at position ' + i
  ENDIF
  i ← i + 1
ENDWHILE
IF found = False THEN
  OUTPUT 'Not found'
ENDIF

Advantages & Disadvantages

When to Use Linear Search

✅ ADVANTAGES

Works on unsorted lists — no sorting required

Simple to understand and implement

Best case: 1 comparison (item is first)

❌ DISADVANTAGES

Worst case: n comparisons (item is last or not in list)

Very slow for large datasets

Inefficient compared to binary search on sorted data

Exam Practice

Have a go at this question

AQA-style question

The list [4, 12, 7, 19, 3, 8, 21] is searched using linear search for the value 8. How many comparisons are needed? Explain why linear search does not require the list to be sorted.

3 marks

MARK SCHEME

6 comparisons [1]. Linear search checks each item in order from the beginning [1]. It doesn't need to jump to a midpoint, so the list doesn't need to be in any particular order [1].

Key Takeaways

What to Remember

Linear search checks items one by one from the start

Does NOT need a sorted list — this is its key advantage

Best case: 1 comparison · Worst case: n comparisons

Inefficient for large datasets — use binary search on sorted data instead