B2.4 · Searching · Covered

Linear search

Find the first matching value by checking items in order. Revisit the lesson and practise the stopping condition.

55 minutes

For this lesson

Open student handout (PDF) Class activities ↓ Try the example in Python →

Animations: Linear search Binary search

Python · step by step

Linear search

Example

Check values in order; stop at the first match.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def linear_search(items, target):2    for index in range(len(items)):3        if items[index] == target:4            return index5    return -1

Speed

Execution progress

The first item is the best case, O(1). The last item or an absent target takes O(n) time. This implementation uses O(1) auxiliary space.

By the end of this lesson

Return the first matching index or -1 when the target is absent.
Trace the algorithm and count comparisons.
Test empty lists, repeated values and boundary positions.

Use these activities to review the topic at your own pace. Timings are approximate.

Review the lesson

01 · 5 minutes

Retrieve

Explain how a stack and a queue differ. Then predict the result of traversing a Python list by index.

02 · 10 minutes

Design

Use numbers = [7, 3, 9, 2, 6] and target = 9. Describe how you would find the value without using in or index().

03 · 10 minutes

Trace

Track the index, current value, comparison and result. Compare stopping at the first match with continuing to the end.

04 · 20 minutes

Implement

Write find_first(items, target). Return the first matching index; return -1 only after all candidates have been checked. Test [], [4], and [4, 7, 4] with present and absent targets.

05 · 10 minutes

Explain

Explain best and worst cases. Count comparisons when the target is first, last or absent. Describe what changes if the data is sorted.

Space complexity: what are we counting?

Auxiliary space means the extra working memory an algorithm needs, beyond the input it has already been given. Think of it as scratch space: counters, a running total, new lists and the memory used by active function calls.

In the summation example on textbook page 361, numbers is the supplied input list. The algorithm keeps a running total in sum and uses a fixed number of extra variables. Whether the list has 10 items or 10,000, it still needs only those few variables: O(1) auxiliary space.

The textbook’s O(n) space statement counts the input list too: storing n items takes memory that grows with n. That is total space, including the input. Both descriptions can be correct; they count different things.

A larger value in sum does not mean we keep more totals. For this classroom analysis, we treat each number as one fixed-size value. Creating a new copy of all n items, or saving every intermediate total, would instead need O(n) auxiliary space.

When explaining an answer, state your convention: “O(1) auxiliary space; O(n) total space including the input list.” Time is a separate question: visiting every item still takes O(n) time.

Before you leave

Exit question

Why must return -1 come after the loop rather than after the first failed comparison?