3.1.3a Linear Search — AQA 8525

What is Linear Search?

Linear search (also called sequential search) is a searching algorithm that checks each element in a list one by one, from the first to the last, until either the target is found or the entire list has been checked.

It works on any list — sorted or unsorted. It is the simplest searching algorithm.

How Linear Search Works — Step by Step

Start at the first element (index 0)
Compare the current element to the target
If they match → return the index (found!)
If they don't match → move to the next element
Repeat until found or end of list reached
If end of list reached without a match → return "not found"

Visual Trace — Searching for 7 in [3, 1, 7, 9, 4]

Target = 7

Step 1: Check 3 ≠ 7 → move on

Step 2: Check 1 ≠ 7 → move on

Step 3: 7 = 7 ✓ Found at index 2!

AQA Pseudo-code

SUBROUTINE linearSearch(list, target)
    found ← False
    position ← -1
    FOR i ← 0 TO LEN(list) - 1
        IF list[i] = target THEN
            found ← True
            position ← i
        ENDIF
    ENDFOR
    RETURN position   // returns -1 if not found
ENDSUBROUTINE

Trace Table for [3, 1, 7, 9, 4], target = 7

i	list[i]	list[i] = target?	found	position
0	3	False	False	-1
1	1	False	False	-1
2	7	True	True	2
3	9	False	True	2
4	4	False	True	2

Returns: 2 (target found at index 2)

Efficiency of Linear Search

Case	Comparisons	Example (n=10)
Best case	1	Target is the first element
Average case	n ÷ 2	~5 comparisons
Worst case	n	10 comparisons (last or not found)

For n = 1,000,000 items, linear search needs up to 1,000,000 comparisons in the worst case.

Advantages and Disadvantages

Advantages	Disadvantages
Works on unsorted lists	Slow for large lists (up to n comparisons)
Simple to implement and understand	Less efficient than binary search on sorted data
No preprocessing needed	Not suitable for very large datasets

Exam tip: Linear search works on both sorted and unsorted lists. Binary search is faster but requires sorting first. If the question says "unsorted list", linear search is the correct algorithm to use.

⚠️ Common Mistakes

Saying linear search requires a sorted list — it does NOT
Stopping the trace table early if the item is found — in the basic algorithm above, the loop continues to the end
Confusing "not found" (returns -1 or False) with an error
Giving the wrong index — lists in AQA are usually zero-indexed (first element = index 0)

▶

Video coming soon

This lesson video is in production

Key points covered in this video

What linear search is and how it works step by step
Visual walkthrough: searching for 7 in [3, 1, 7, 9, 4]
AQA pseudo-code for linear search
Completing a trace table for a linear search
Best, average and worst case — and why linear search can be slow

Click slide or press arrow keys to navigate

✍️

Exam-style Worksheet — 3.1.3a Linear Search

8 AQA-style questions · 22 marks · AI marks your answers and gives feedback

Q1Describe how a linear search works.[3 marks]

✅ Mark scheme

Mark scheme

Starts at the first element [1]; compares each element to the target one by one [1]; returns the position if found, or indicates not found if the end of the list is reached [1].

Q2Trace a linear search for target = 9 in the list [5, 2, 9, 3, 7]. How many comparisons are made and what is returned?[3 marks]

✅ Mark scheme

Mark scheme

i=0: 5≠9; i=1: 2≠9; i=2: 9=9 → found [2 for all steps correct, 1 if 2 steps correct]; 3 comparisons [1]; returns index 2 / position 3 (1-indexed) [1]. Award up to 3.

Q3What does linear search return if the target is not in the list?[1 mark]

✅ Mark scheme

Mark scheme

It returns -1 (or False / "not found" / an indication that the item is not in the list) [1].

Q4State the worst-case number of comparisons for a linear search on a list of n items, and describe when this occurs.[2 marks]

✅ Mark scheme

Mark scheme

n comparisons [1]; this occurs when the target is the last element in the list, or is not in the list at all [1].

Q5Give one advantage and one disadvantage of linear search compared to binary search.[2 marks]

✅ Mark scheme

Mark scheme

Advantage: works on unsorted lists / simpler to implement [1]; Disadvantage: slower for large lists / needs up to n comparisons vs log₂(n) for binary search [1].

Q6Write the AQA pseudo-code for a linear search on a list called 'data' searching for a value called 'target'. Use a FOR loop.[4 marks]

✅ Mark scheme

Mark scheme

FOR i ← 0 TO LEN(data) - 1 [1]; IF data[i] = target THEN [1]; set found ← True and/or position ← i [1]; ENDIF / ENDFOR with correct structure [1]. (Award marks for equivalent correct logic)

Q7A database of 500,000 unsorted records needs to be searched. Explain why linear search is used here instead of binary search.[3 marks]

✅ Mark scheme

Mark scheme

Binary search requires a sorted list [1]; sorting 500,000 unsorted records first would take significant time and processing [1]; linear search works directly on unsorted data, making it appropriate here despite the higher number of comparisons [1].

Q8A linear search checks a list of 20 items for a target that is not present. How many comparisons are made? What is the best-case number of comparisons for a list of 20 items?[4 marks]

✅ Mark scheme

Mark scheme

Not present → 20 comparisons (all items checked) [1 mark + 1 explanation]; Best case: 1 comparison [1]; this occurs when the target is the first element in the list [1].

✓

Compare your answers to the mark schemes above.

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 5

Click to flip

🎉

All cards reviewed!

Term	Definition

🔒

Pro Content

Subscribe to unlock all AQA 8525 lessons, worksheets, quizzes and mini tests.

£7.99/month

or £59/year

Upgrade to Pro

What is Linear Search?

How Linear Search Works — Step by Step

Visual Trace — Searching for 7 in [3, 1, 7, 9, 4]

AQA Pseudo-code

Trace Table for [3, 1, 7, 9, 4], target = 7

Efficiency of Linear Search

Advantages and Disadvantages

Key points covered in this video

Exam-style Worksheet — 3.1.3a Linear Search

Mini Test — 3.1.3a Linear Search