Линейный поиск

Линейный поиск (Linear Search): последовательный просмотр массива, код на Python, сложность O(n) и когда это единственный вариант.

Линейный поиск — самый прямолинейный способ найти элемент: просматриваем каждый элемент массива слева направо до тех пор, пока не найдём нужный или не дойдём до конца.

Сложность: O(n) в среднем и худшем случае; O(1) в лучшем (первый элемент).

Идея алгоритма

Никакого предварительного условия — массив может быть неотсортированным. Просто проверяем элементы один за другим. Как искать потерянный ключ, осматривая карман за карманом.

Пошаговый разбор

Массив [4, 2, 9, 7, 5], ищем 7:

Код

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i      # вернём индекс первого вхождения
    return -1             # не найден

data = [4, 2, 9, 7, 5]
idx = linear_search(data, 7)
print(f"Индекс: {idx}")          # 3

idx2 = linear_search(data, 99)
print(f"Индекс: {idx2}")         # -1

Вывод:

Индекс: 3
Индекс: -1

Сложность и свойства

Память: O(1). Работает на любых данных — отсортированных, неотсортированных, с дубликатами.

Когда применять

• Массив не отсортирован и сортировать его нет смысла.
• Массив маленький — разница между O(n) и O(log n) незначительна.
• Нужно найти все вхождения элемента (не только первое).
• Данные в связном списке — бинарный поиск там неприменим.

Если массив большой и поиск выполняется многократно — стоит один раз отсортировать и использовать бинарный поиск.

Коротко

• Линейный поиск проверяет каждый элемент по очереди; возвращает индекс или −1.
• O(n) в среднем — медленнее бинарного на больших массивах.
• Не требует сортировки; подходит для любых структур данных.
• Простейший алгоритм поиска; хорош для маленьких или неотсортированных наборов.