Python linear search

Find the first matching element without assuming sorted input.

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

Explanation

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.

Explore the dry run

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

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.

Python linear search

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading