Linear Search

Search a list one item at a time, then write the algorithm and work out how many comparisons it needs.

About 3 min read
  • Describe how linear search works
  • Write a linear search in Python
  • Compare best-case and worst-case searches
Before you start

You can use lists, loops and if statements. A search algorithm combines all three.

Checking each item

Linear search looks through a list from the start. It compares each item with the target. If it finds a match, it stops. If it reaches the end without a match, the target is not in the list. The list does not need to be sorted, so linear search works on any data.

Definition: linear search

A search that checks each item in order until it finds the target or reaches the end.

Definition: target

The value that a search algorithm is looking for.

Efficiency

In the best case, the target is first and only 1 comparison is needed. In the worst case, the target is last or missing, so all n items are checked. On average, a search through a list checks about half of the items when the target is present.

Search in Python

Write a function that returns the position of a target, or −1 if it is missing.

Python
def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

Searching [4, 9, 2] for 2 checks 4, then 9, then 2, and returns position 2.

Return only after the loop

Put return -1 after the loop. Inside the loop, it would stop after checking the first item.

Exam focus
Say it like this“Compare the target with each item in turn until it is found or the list ends.”
Not like this“Look through the list.” — Describe the comparison and the stopping condition.
Common mistakeSaying that linear search needs sorted data. It works on sorted and unsorted lists.

Practice

How many comparisons are needed to find 7 in [7, 2, 9]?
1 comparison.
How many comparisons are needed to find 9 in [7, 2, 9]?
3 comparisons.
Does linear search need a sorted list?
No.
Going further
A list has 1000 items and the target is missing. How many comparisons does linear search make, and why?
1000, because it must check every item before it can say the target is missing.

Quick check

Linear search quick check

Where does linear search begin?

It moves through positions in order, checking each one in sequence.

What is the worst case for a list of n items?

The target is last or missing, so every item must be checked.

When should a linear search stop early?

A match means the job is complete, so further checks are unnecessary.
Key takeaways
  • Linear search checks items in order.
  • It stops when it finds the target.
  • It works on unsorted lists.
  • The worst case checks all n items.
Back to Grade 10 chaptersRelated resources →