Lesson 4 of 8
Theory hub Algorithms Lesson 4
Algorithms: Lesson 4

Linear Search

The simplest searching algorithm: check every element one by one until you find what you are looking for - or confirm it is not there. Includes an interactive step-through visualiser and full complexity analysis.

45 minutes Interactive search visualiser
Pseudocode style: Saved automatically
Why this matters

You perform a linear search every time you look for your keys. You check your coat pocket, then your bag, then the kitchen counter - one location at a time, in order, until you find them or run out of places to look. Computers do exactly the same thing when searching an unsorted list. It is not glamorous, but it is reliable, universal and the starting point for understanding all searching algorithms.

Think about it: You have a list of 1,000 phone numbers in no particular order. You want to find whether a specific number appears in the list. How many numbers might you need to check before you can be certain? What is the absolute best case? What is the worst case? Estimate the average. These three questions define the efficiency of any algorithm.
Key terms
Terms you need to know
Linear search
A search algorithm that checks each element of a list one by one, starting from the first, until the target is found or the list is exhausted.
Sequential search
Another name for linear search - emphasises that elements are examined in sequence, one after another.
Best case
The most favourable input for an algorithm. For linear search: the target is the first element. Only 1 comparison needed.
Worst case
The least favourable input. For linear search: the target is the last element, or not in the list. n comparisons needed for a list of n items.
Average case
The typical expected performance. For linear search: n/2 comparisons on average for a list of n items.
Unsorted list
A list whose elements are in no particular order. Linear search can be used on unsorted lists; binary search cannot.
How it works
The algorithm step by step

Linear search is straightforward: start at index 0 and check each element in turn. If the current element matches the target, return the index and stop. If you reach the end of the list without finding the target, return -1 (or a flag indicating "not found").

The algorithm works on any list, sorted or unsorted. This is its key advantage over binary search, which requires the list to be sorted first.

StepActionCondition
1Start at index 0-
2Compare current element to targetIf equal, return current index and stop
3Move to next element (index + 1)If we have reached the end of the list, go to step 4
4 (loop)Repeat step 2 and 3Continue until found or end reached
5Return -1 (not found)Only reached if loop completed without finding target
A concrete example

Search for 7 in the list [3, 9, 1, 7, 5, 2]:
Index 0: 3 = 7? No. Move on.
Index 1: 9 = 7? No. Move on.
Index 2: 1 = 7? No. Move on.
Index 3: 7 = 7? Yes! Return index 3.
The search took 4 comparisons out of 6 elements.

Pseudocode
Writing the linear search algorithm

The pseudocode below implements a linear search as a function/subroutine that takes the list and the target value as parameters and returns the index where the target was found, or -1 if it was not found.

// Linear search - returns index of target or -1 (AQA)
SUBROUTINE linearSearch(myList, target)
    found ← FALSE
    index ← -1
    i ← 0
    WHILE i < LEN(myList) AND found = FALSE
        IF myList[i] = target THEN
            found ← TRUE
            index ← i
        ENDIF
        i ← i + 1
    ENDWHILE
    RETURN index
ENDSUBROUTINE
# Linear search - returns index of target or -1 (OCR)
function linearSearch(myList, target)
    found = false
    index = -1
    i = 0
    while i < len(myList) and found == false
        if myList[i] == target then
            found = true
            index = i
        end if
        i = i + 1
    end while
    return index
endfunction
Exam angle

Exam questions on linear search often ask you to: (1) Trace the algorithm with a given list and target, showing the value of i at each step. (2) State how many comparisons were needed. (3) Write or complete the pseudocode. Know that returning -1 is the conventional way to signal "not found" - returning 0 would be ambiguous (index 0 is a valid position). Also know that the algorithm exits the WHILE loop as soon as found becomes TRUE, so it does not continue checking remaining elements after the target is found.

Worked trace
Tracing a linear search

Trace a linear search for target = 7 in myList = [4, 2, 9, 7, 1, 6]:

imyList[i]myList[i] = 7?foundindex
04NoFALSE-1
12NoFALSE-1
29NoFALSE-1
37YesTRUE3
Loop condition: found = TRUE, so loop exits. RETURN 3.

4 comparisons were needed to find the target at index 3. Note: the loop exits immediately when found = TRUE, so elements at indices 4 and 5 are never checked.

Now trace for target = 8 (not in the list):

imyList[i]myList[i] = 8?foundindex
04NoFALSE-1
12NoFALSE-1
29NoFALSE-1
37NoFALSE-1
41NoFALSE-1
56NoFALSE-1
i reaches 6 = LEN(myList). Loop exits. RETURN -1 (not found).

All 6 comparisons were needed to confirm 8 is not in the list. This is the worst case: n comparisons for a list of n items.

Efficiency analysis
Best, worst and average case

Analysing an algorithm's efficiency means asking: how does the number of steps grow as the input size (n) increases? For linear search, this is straightforward.

CaseScenarioComparisons neededExample (n=100)
Best caseTarget is at index 0 (first element)11 comparison
Average caseTarget is somewhere in the middlen / 250 comparisons
Worst caseTarget is last, or not in the listn100 comparisons
When to use linear search

Use linear search when:
- The list is small (the inefficiency does not matter)
- The list is unsorted (binary search requires a sorted list)
- The list is constantly changing (re-sorting for binary search would be expensive)
- You are searching for all occurrences, not just the first

Avoid linear search when:
- The list is large and sorted - binary search is dramatically faster

Exam angle

A very common exam question: "Compare linear search and binary search. State one advantage of linear search over binary search." The answer: linear search works on unsorted lists; binary search requires the list to be sorted. Also know: "State the worst-case number of comparisons for a linear search on a list of 50 items." Answer: 50.

Interactive visualiser
Watch linear search step by step

Enter a target value and press Step to watch the algorithm check each element one by one. Orange = currently checking. Green = found.

Enter a target value and press Start search.
Quick quiz

Test yourself

1. A linear search is performed on a list of 40 items. The target is the very last element. How many comparisons are made?

40 comparisons. The target is at the last position, so every element before it must be checked and found not to match. This is the worst case for linear search. (Some might argue 39 preceding elements plus 1 match = 40 total, which is the same answer.)

2. What does a linear search return if the target is not found in the list?

By convention, -1 is returned to indicate the target was not found. Returning 0 would be ambiguous since 0 is a valid index. The exact value used can vary (some use False, None or a boolean flag) but -1 is the standard GCSE answer.

3. Which statement about linear search is correct?

Linear search works on any list regardless of order. This is its main advantage over binary search, which requires a sorted list. Linear search checks elements one by one - it never divides the list.

4. What is the average-case number of comparisons for a linear search on a list of 200 items?

On average, the target is found halfway through the list, so about n/2 = 200/2 = 100 comparisons. Compare this to binary search, which would find the target in at most log2(200) = 8 comparisons in the worst case - a massive improvement for large sorted lists.

5. A student says "linear search is useless because binary search is always better." Give one reason this is wrong.

Binary search requires the list to be sorted before the search begins. If the list is unsorted, binary search cannot be used at all. Linear search works on any list. For small or frequently changing lists, the overhead of sorting for binary search may outweigh the benefits.
Think deeper
Challenge question

A developer needs to search a list of 1,000,000 employee names to check if a given name exists. The names are stored in alphabetical order. They are deciding between linear search and binary search. Calculate the worst-case number of comparisons for each algorithm and explain which they should choose, and why the other might still be used in some circumstances.

Linear search worst case: 1,000,000 comparisons (must check every element).

Binary search worst case: log2(1,000,000) = approximately 20 comparisons (since 2^20 = 1,048,576).

Choice: Binary search is dramatically more efficient - 20 vs 1,000,000 comparisons in the worst case. Since the list is already sorted, binary search should be used.

When linear might still be used:
- If searching for all employees with a given name (binary search finds one match; linear search finds all)
- If the list is frequently updated with new employees in random positions (maintaining sort order adds overhead)
- If the list is very short and the simplicity of linear search is worth the slight performance cost
Lesson 3 Lesson 5: Binary Search
Printable Worksheets

Practice what you have learned

Three levelled worksheets. Download, print and complete offline.

Recall
Linear Search Fundamentals
Define key terms, fill in the algorithm steps and state best/worst/average case comparisons.
Download
Apply
Tracing Linear Search
Trace three linear searches with different lists and targets, completing full trace tables for each.
Download
Exam Style
Exam-Style Questions
Complete and correct pseudocode, trace an algorithm, compare to binary search, and justify algorithm choice for a given scenario.
Download
Lesson 4 - Algorithms
Linear Search
Starter activity
Give each student a set of 15 shuffled number cards (or write 15 numbers on the board in random order). Ask them to find the number 7 (or another specific value). Ask: "How did you search? Did you look at every card in order?" Most students naturally perform a linear search. Ask: "How many cards did you check? What is the maximum you might have needed to check?" This grounds the algorithm in physical intuition.
Lesson objectives
1
Describe how linear search works and trace it step by step with a given list and target.
2
Write pseudocode for linear search that correctly handles "found" and "not found" cases.
3
State the best, worst and average case number of comparisons for a list of n items.
4
Identify when linear search is the appropriate choice over binary search.
5
Compare linear search to binary search in terms of efficiency and requirements.
Key vocabulary
Linear search
Check each element one by one in sequence. Works on sorted or unsorted lists.
Best case
Target is first element. 1 comparison.
Worst case
Target is last or not present. n comparisons for n items.
Average case
Target is somewhere in the middle. n/2 comparisons on average.
Discussion questions
In what real-world situations is linear search the only option?
If you have a list of 1,000,000 items that is already sorted, how many comparisons does binary search need in the worst case? How does this compare to linear search?
Why does the algorithm return -1 for "not found" rather than 0 or False?
Exit tickets
State the worst-case number of comparisons for a linear search on a list of 80 items. [1 mark]
Give one advantage of linear search over binary search. [1 mark]
A linear search for 5 in [8, 3, 5, 1, 9] returns 2. Explain why. [2 marks]
Homework suggestion
Write a modified linear search algorithm that finds and returns all indices where the target appears in the list (not just the first). Trace it on the list [3, 7, 2, 7, 9, 7, 1] with target = 7. Then explain how this differs from the standard linear search that returns only the first match.
Resources
Worksheet 1 - Recall Worksheet 2 - Apply Worksheet 3 - Exam Style Unit Exam Paper