Python linear search

Find the first matching element without assuming sorted input.

On this page

Before you start

Lists, loops, and return values.

Find the first matching element without assuming sorted input.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Linear search checks elements from left to right. Returning immediately on equality finds the first occurrence.

The return value -1 means no match. Callers must check that sentinel before using it as a Python index, because index -1 normally selects the last item.

Code example

Python

def find(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

print(find([4, 9, 2, 9], 9))
print(find([4, 9, 2, 9], 7))
assert find([], 9) == -1
assert find([9], 9) == 0

Output

1
-1

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1def find(values, target):

2 for index, value in enumerate(values):

3 if value == target:

4 return index

5 return -1

7print(find([4, 9, 2, 9], 9))

8print(find([4, 9, 2, 9], 7))

9assert find([], 9) == -1

10assert find([9], 9) == 0

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Search for 9.	`target = 9`	—
Compare index 0: 4 is not 9.	`index = 0, value = 4`	—
Compare index 1: 9 matches.	`index = 1, value = 9`	—
Return the first matching index.	`return = 1`	—
Print the successful search.	`return = 1`	1
The second search checks all four items and finds no 7.	`return = -1`	1
Print the missing sentinel.	`return = -1`	1 -1

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

Cost and common mistakes

O(n) worst-case time, O(1) auxiliary space.

Returning -1 inside the loop would stop too early.
Duplicates do not change this contract: the first match wins.

Try it yourself

Find 2 in [4, 9, 2, 9].

Reveal answer and reasoning

The return value is index 2 after three comparisons.