Что такое линейный поиск

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

def linear_search(xs, target):
    for i, x in enumerate(xs):
        if x == target:
            return i
    return -1

Никаких индексов-инвариантов, никаких границ, никаких предусловий — просто проход. Это самый простой алгоритм поиска и одновременно — самый универсальный. Он работает на любой итерируемой структуре: list, tuple, генератор, файл, поток событий.

Сложность очевидна: в худшем случае мы посмотрим на все n элементов. Среднее — n/2, но в нотации Big-O это всё та же O(n).

Когда O(n) лучше, чем O(log n)

Студентов учат: бинарный поиск быстрее линейного, потому что log(n) меньше n. Это правда — асимптотически. На практике у линейного поиска есть три серьёзных преимущества.

Первое — он работает на любой структуре. Не нужна сортировка. Не нужен random access. Достаточно итерации. Поэтому линейный поиск — единственный вариант, если у вас:

• неотсортированный массив,
• связный список (random access O(n), бинарный поиск теряет смысл),
• генератор или поток,
• файл, который читается построчно.

Второе — он cache-friendly. Идти подряд по непрерывному блоку памяти — лучший доступ для процессора. Префетчер CPU заранее тянет соседние cache-линии, и каждое следующее чтение почти бесплатное. Бинарный поиск, наоборот, прыгает по середине, четверти, восьмой части — это random access, и каждый прыжок может быть cache miss на 100 тактов.

Третье — на маленьких коллекциях он просто быстрее. Накладные расходы (вычисление середины, проверка границ, ветвление) у бинарного поиска заметные. Эксперимент: при n < 30 обычно линейный поиск выигрывает. В реальных реализациях стандартных библиотек (например, в Java TimSort) бинарный поиск переключается на линейный, когда фрагмент короче ~7 элементов.

Поиск с предикатом

В Python линейный поиск чаще выглядит не как «найти равное», а как «найти первое подходящее»:

# первое чётное число
result = next((x for x in xs if x % 2 == 0), None)

# первый элемент, начинающийся с "user_"
first_user = next((s for s in events if s.startswith("user_")), None)

# все элементы старше 30 минут
fresh = [e for e in events if e.timestamp > now - 1800]

Это всё линейные проходы, но с предикатом — произвольным условием. Бинарный поиск тут невозможен: условие может быть произвольно сложным, а не просто x == target.

Многие задачи Data Engineer — это линейные проходы с предикатом: «отфильтруй события за последний час», «найди первый сбой в логе», «посчитай записи с ошибкой». На сотнях тысяч записей это O(n), и никакая структура данных не сделает быстрее, если предикат произвольный.

Python in и index — это линейный поиск для list

Стоит запомнить одну вещь, которая ускользает от джунов: оператор in и метод .index() для list — это линейные операции.

xs = list(range(1_000_000))

# O(n) — обход всего списка пока не найдём
print(999_999 in xs)        # медленно: проход почти до конца
print(xs.index(999_999))    # та же история

# для проверки наличия лучше set
xs_set = set(xs)
print(999_999 in xs_set)    # O(1), хеш-поиск

Это критично знать: код вида if user_id in users_list на миллионе пользователей — это миллион сравнений за каждый вызов. Если такая проверка делается в цикле — получаем O(n²) и серверный таймаут.

Замеры

Простой эксперимент: ищем число в разных структурах разного размера.

import timeit

n = 1_000_000
xs_list = list(range(n))
xs_set = set(xs_list)
target = n - 1   # последний элемент — худший случай для линейного поиска

# linear search через in
t_list = timeit.timeit(lambda: target in xs_list, number=10)
# hash lookup
t_set = timeit.timeit(lambda: target in xs_set, number=10)

print(f"list (O(n)): {t_list * 1000:.2f} ms")    # ~150 ms
print(f"set  (O(1)): {t_set * 1000:.4f} ms")     # ~0.0005 ms

Разница в 300 000 раз. Это не «set чуть быстрее» — это разные алгоритмические классы.

Но если изменить target на первый элемент (target = 0), linear search выиграет:

target = 0
t_list = timeit.timeit(lambda: target in xs_list, number=10)
# ~0.0001 ms — нашли мгновенно

В этом и суть линейного поиска: его время сильно зависит от позиции искомого элемента. Среднее — n/2, но если элемент почти всегда в начале, реальная скорость отличная.

Когда линейный поиск — лучший выбор

Подведём:

1. Маленькие коллекции (n < 30-50). Накладные расходы бинарного поиска и хеширования съедают теоретическое преимущество.
2. Однократный поиск в неотсортированных данных. Сортировка ради одного поиска — O(n log n) + O(log n) = O(n log n), хуже чем просто O(n).
3. Поиск с произвольным предикатом. Бинарный/хеш-поиск работают только по равенству ключа.
4. Потоковая обработка. В генераторе или файле нет случайного доступа.
5. Поиск первого подходящего элемента. Часто целевой элемент находится в первой трети массива — реальное среднее меньше n/2.

В Data Engineering линейный поиск встречается в каждом ETL: «найди в батче событие с таким идентификатором», «отфильтруй неподходящие». Никакой структуры данных не нужно, если данные используются один раз.

Попробуй сам

Проверьте на себе разницу между in для list и set:

import timeit
import random

n = 100_000
data = list(range(n))
random.shuffle(data)

data_set = set(data)

# ищем 100 случайных элементов
targets = random.sample(range(n), 100)

t_list = timeit.timeit(
    lambda: [t in data for t in targets],
    number=10,
)
t_set = timeit.timeit(
    lambda: [t in data_set for t in targets],
    number=10,
)

print(f"list: {t_list * 1000:.2f} ms")
print(f"set:  {t_set * 1000:.4f} ms")
print(f"speedup: {t_list / t_set:.0f}x")

На моей машине разница около 1000x при n = 100_000. Запустите с разными n — увидите, как масштабируется разница: для set она остаётся постоянной, для list растёт линейно.