Linear search is the simplest search algorithm: we look at the elements in order from left to right. It needs no sorting and works on any sequence. For sorted data there is a faster way: binary search.

![Searching 7 in [4, 9, 2, 7, 5]](img/lessons/algorithms/linear-search-trace.svg)

The algorithm and the invariant

At each step we compare a[i] with x. Invariant: before step i, x is not in a[0..i-1]. When equality is found, i is the first occurrence; when the loop ends, the invariant says x is nowhere in the list, hence -1. On correctness: loop invariants.

python
def linear_search(a, x):
    for i, v in enumerate(a):
        if v == x:
            return i               # first occurrence
    return -1                      # not found

data = [4, 9, 2, 7, 5]
print(linear_search(data, 7))
print(linear_search(data, 8))
print(linear_search([], 1))
text
3
-1
-1

Best, worst and average case