Линейный поиск (linear search) — простейший алгоритм: просматриваем элементы по порядку слева направо. Он не требует сортировки и работает на любой последовательности. Для отсортированных данных есть быстрее: бинарный поиск.

![Поиск 7 в [4, 9, 2, 7, 5]](img/lessons/algorithms/linear-search-trace.svg)

Алгоритм и инвариант

На каждом шаге сравниваем a[i] с x. Инвариант: перед шагом i значения x нет в a[0..i-1]. Когда найдено равенство, i — первое вхождение; когда цикл закончился, инвариант говорит, что x нет во всём списке, поэтому возвращается -1. О корректности: инварианты циклов.

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

Лучший, худший и средний случай