Linear Search

Finding elements by checking each one in sequence — implementation patterns, Python's built-in alternatives, and when to use it.

Linear Search

Given a list of $n$ numbers, linear search finds the index of a target value $x$ by going through the list element by element and checking each one. In the worst case — when the element is at the very end or not present at all — it checks all $n$ elements, giving a time complexity of $O(n)$.

For Loop

While Loop

Both implementations return the index of the first occurrence of x, or -1 if not found.

Python's in Operator

Python has a built-in way to check membership with in:

This is linear search under the hood — it is O(n) just like the manual implementations above. It is convenient, but you should not use it in a tight loop when performance matters.

To get the index, use the list method .index(x):

.index(x) raises a ValueError if x is not in the list. To stay safe, check first:

Note that this calls linear search twice. If you need both safety and a single pass, use the manual implementation.

Searching with a Condition