Linear search and its variations

Worst case on an unsorted list (spec 10.3.1)

The simplest version checks every item, even after a match: it always makes n comparisons. This is needed when you want the last match or every match.

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

print(linear_search_all([4, 9, 2, 9, 5], 9))

Output:

3

Early exit when found (unsorted list)

Stop as soon as the target is found, using a while loop and a found flag (or return inside a for loop). On average this checks about half the list; in the worst case (last item or not present) it still checks all n items.

def linear_search(items, target):
    i = 0
    found = False
    while i < len(items) and not found:
        if items[i] == target:
            found = True
        else:
            i = i + 1
    if found:
        return i
    return -1

print(linear_search([4, 9, 2, 9, 5], 9), linear_search([4, 9, 2], 7))

Output:

1 -1

Early exit on a sorted list

If the list is in ascending order you can stop early in two ways: when the target is found, and when you reach an item greater than the target, because the target cannot appear later.

def sorted_linear_search(items, target):
    i = 0
    while i < len(items) and items[i] < target:
        i = i + 1
    if i < len(items) and items[i] == target:
        return i
    return -1

data = [3, 8, 12, 15, 21, 30]
print(sorted_linear_search(data, 15), sorted_linear_search(data, 13))

Output:

3 -1

Searching for 13 stops at 15 after 4 comparisons instead of checking all 6 items.

Worked example

How many items are examined when searching [7, 3, 9, 1, 6] for 1 with early exit, and for 4?

1. For 1: 7, 3, 9, 1: found at index 3 after 4 comparisons
2. For 4: every item is checked: 5 comparisons, then -1 is returned

Answer: 4 comparisons, then 5 comparisons

Check yourself

1. What is displayed when this code runs? ```python def linear_search(items, target): for i in range(len(items)): if items[i] == target: return i return -1 print(linear_search(["ox", "cat", "emu", "cat"], "cat")) ```
   Show answer

   1. return exits at the first match, at index 1.

2. What is displayed when this code runs? ```python def last_index(items, target): position = -1 for i in range(len(items)): if items[i] == target: position = i return position print(last_index(["ox", "cat", "emu", "cat"], "cat")) ```
   Show answer

   3. No early exit, so the last match wins: index 3.

3. Using early exit, how many comparisons are made when searching [5, 2, 8, 6, 1, 9] for 6?
   Show answer

   4. 5, 2, 8, 6: the target is found on the 4th comparison.

4. A sorted-list linear search with early exit looks for 20 in [4, 10, 17, 23, 31, 40]. How many items does it examine before stopping?
   Show answer

   4. It examines 4, 10, 17 and then 23; 23 > 20, so 20 cannot be in the list and it stops after 4 items.

5. In the worst case, how many comparisons does a linear search make on a list of 250 items?
   Show answer

   250. If the item is last or missing, every item is checked: 250.

6. This sorted-list search should return -1 for a missing target without checking every item. Which line completes it? ```python def search(items, target): i = 0 __________ i = i + 1 if i < len(items) and items[i] == target: return i return -1 print(search([2, 5, 9, 14], 9), search([2, 5, 9, 14], 6), search([2, 5, 9, 14], 20)) ```
   • `while i < len(items) and items[i] < target:`
   • `while items[i] < target:`
   • `while i < len(items) and items[i] > target:`
   • `while i <= len(items) and items[i] < target:`
   Show answer

   `while i < len(items) and items[i] < target:`. Keep going only while there are items left and the current item is smaller than the target.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (XCP01/YCP01), first teaching 2026
• Pearson IAL Computer Science Unit 2 Programming Language Subset (PLS), Python 3
• Pearson IAL Computer Science IAS sample assessment materials (Unit 2 paper and mark scheme)

Last updated 8 November 2026. Spotted a mistake? Tell us.