Алгоритмы поиска: линейный и бинарный

Линейный поиск проверяет элементы по одному и работает на любом списке. Бинарный поиск на каждом шаге отбрасывает половину отсортированного списка и находит элемент намного быстрее. Статья для тех, кто умеет писать циклы на Python и уже знаком с сортировкой. Вы напишете оба поиска, посмотрите бинарный поиск по шагам, сравните число сравнений на списках до миллиона элементов и увидите, когда бинарный поиск ошибается.

Описания алгоритмов сверены с Википедией, разбор ошибки — с записью Джошуа Блоха на блоге Google Research, средства Python — с документацией. Код проверен запуском на Python 3.13. Данные на октябрь 2026 года.

Задача поиска

Нужно найти в списке элемент с заданным значением и вернуть его номер. Если такого элемента нет, возвращают признак «не найдено», например −1. Википедия определяет алгоритм поиска как алгоритм для решения задач поиска и замечает, что выбор подходящего алгоритма часто зависит от структуры данных и от того, что известно о данных заранее.

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

Идея самая простая: просматриваем элементы слева направо и сравниваем каждый с искомым. По Википедии, линейный поиск — простейший алгоритм, который не накладывает ограничений на данные, а его асимптотическая сложность — O(n).

def линейный(данные, цель):
    """Возвращает (индекс или -1, число сравнений)."""
    сравнений = 0
    for i, x in enumerate(данные):
        сравнений += 1
        if x == цель:
            return i, сравнений
    return -1, сравнений

Бинарный поиск

Идея похожа на игру «угадай число»: вы загадали число от 1 до 100, вас спрашивают про середину, а вы отвечаете «больше» или «меньше». Википедия описывает алгоритм так: определяют значение элемента в середине структуры данных и сравнивают с ключом. Если ключ меньше, поиск продолжают в первой половине, иначе во второй. Процесс повторяют, пока не найдут элемент или пока интервал поиска не станет пустым.

Шаг 1. Задайте границы

Нижняя граница — индекс первого элемента, верхняя — индекс последнего.

Шаг 2. Найдите середину

Возьмите элемент посередине между границами.

Шаг 3. Сравните с искомым

Если середина равна искомому, поиск закончен. Если середина меньше искомого, искать надо правее. Если больше — левее.

Шаг 4. Отбросьте половину

Сдвиньте нижнюю или верхнюю границу за середину и вернитесь к шагу 2. Если границы разошлись, элемента в списке нет.

def бинарный(данные, цель, показывать=False):
    """Возвращает (индекс или -1, число сравнений). Список должен быть отсортирован."""
    низ, верх = 0, len(данные) - 1
    сравнений = 0
    while низ <= верх:
        середина = низ + (верх - низ) // 2      # середина без переполнения
        сравнений += 1
        if показывать:
            print(f"  границы [{низ}, {верх}], середина {середина}, значение {данные[середина]}")
        if данные[середина] == цель:
            return середина, сравнений
        if данные[середина] < цель:
            низ = середина + 1
        else:
            верх = середина - 1
    return -1, сравнений

Запустим поиск числа 45 в отсортированном списке из 12 чисел:

числа = [3, 8, 12, 17, 21, 26, 31, 40, 45, 52, 60, 71]
print("ищем 45 в отсортированном списке:")
print(бинарный(числа, 45, показывать=True))

ищем 45 в отсортированном списке:
  границы [0, 11], середина 5, значение 26
  границы [6, 11], середина 8, значение 45
(8, 2)

Первая середина — число 26. Оно меньше искомого, поэтому левая половина отброшена. Вторая середина — 45, элемент найден за два сравнения. Линейному поиску потребовалось бы девять.

Сколько шагов нужно

Сложность бинарного поиска, по Википедии, — O(log n) в худшем и среднем случаях, а в лучшем — O(1), когда искомое лежит ровно посередине. Линейный поиск — O(n). Словами: время бинарного поиска растёт на один шаг при удвоении списка, а время линейного — удваивается вместе со списком.

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

print("размер списка  линейный (худший)  бинарный (худший)")
for размер in (10, 1_000, 1_000_000):
    данные = list(range(0, размер * 2, 2))      # чётные числа по возрастанию
    # худший случай бинарного поиска — максимум по всем искомым значениям, в том числе отсутствующим
    худший_бинарный = max(бинарный(данные, x)[1] for x in range(-1, размер * 2 + 1))
    _, худший_линейный = линейный(данные, -1)     # отсутствующий элемент: линейный проверяет весь список
    print(f"{размер:>13}  {худший_линейный:>17}  {худший_бинарный:>17}")

размер списка  линейный (худший)  бинарный (худший)
           10                 10                  4
         1000               1000                 10
      1000000            1000000                 20

Список вырос в сто тысяч раз, а число шагов бинарного поиска — с 4 до 20. Измерения выполнены на условных данных: целые числа по возрастанию.

Когда бинарный поиск не работает

Бинарный поиск решает, куда идти, по значению в середине, поэтому ему нужен отсортированный список. Если порядка нет, отброшенная половина может содержать искомый элемент.

неупорядоченный = [40, 3, 31, 8, 52, 12]
print("в списке есть 8, бинарный поиск нашёл:", бинарный(неупорядоченный, 8)[0])

в списке есть 8, бинарный поиск нашёл: -1

Число 8 в списке есть, но поиск вернул −1: он сравнил середину, увидел 31, отбросил правую половину и до 8 уже не дошёл. Поэтому сначала проверьте или обеспечьте сортировку, а если её нет, используйте линейный поиск или отсортируйте список заранее.

Типичные ошибки реализации

Бинарный поиск кажется простым, но реализовать его верно трудно. Блох цитирует Бентли: первый бинарный поиск опубликовали в 1946 году, а первый, который работает правильно для любого размера списка, появился только в 1962-м. Сам Блох признаётся, что в его версии для JDK была та же ошибка, и она проявилась лишь спустя годы.

Проверяйте три места.

• Границы. Условие цикла низ <= верх и сдвиги середина + 1, середина - 1. Если ошибиться на единицу, цикл может не завершиться или пропустить элемент.
• Середина отрезка. В записи Джошуа Блоха на блоге Google Research разобран случай, когда (low + high) / 2 ломается: сумма границ превышает максимальное значение int (2³¹ − 1), переполняется и становится отрицательной. Ошибка проявляется на массивах от примерно миллиарда элементов. Безопасная запись — низ + (верх - низ) // 2, как в нашем коде.
• Короткие списки. Проверяйте поиск на списках из 0, 1 и 2 элементов.

В Python эта ошибка не возникает: документация сообщает, что целые числа имеют неограниченную точность, поэтому сумма не переполнится. Но запись через разность полезна, если вы переносите алгоритм в другой язык.

Готовые средства Python

Оператор in и метод list.index просматривают список по порядку. Python Wiki оценивает проверку x in s для списка как O(n). Для отсортированных списков есть модуль bisect. По документации, он использует алгоритм деления пополам, но его функции находят место вставки, а не конкретное значение. Документация показывает, как превратить это в поиск: найти место через bisect_left и проверить, что на этом месте стоит искомое.

from bisect import bisect_left

числа = [3, 8, 12, 17, 21, 26, 31, 40, 45, 52, 60, 71]

print(45 in числа)                  # линейный просмотр
print(числа.index(45))              # индекс первого равного, тоже линейный просмотр

i = bisect_left(числа, 45)          # бинарный поиск места вставки
print(i, i < len(числа) and числа[i] == 45)
print(bisect_left(числа, 50))       # где 50 стояло бы в списке

True
8
8 True
9

Для рабочего кода берите готовые средства, а свою реализацию пишите для обучения: так меньше риск ошибок на границах.

Не путать с поиском в интернете

Алгоритмы этой статьи ищут значение в списке. Поиск в интернете подбирает документы по запросу и устроен иначе. Википедия отмечает, что поисковые машины используют алгоритмы поиска, но относятся к области информационного поиска, а не алгоритмики.

Условия и ограничения

Версия

Python 3.13, октябрь 2026 — код проверен запуском; поведение bisect и int описано по документации.

Данные

Список отсортирован — бинарный поиск требует отсортированных данных, иначе результат неверен.

Размер

На коротких списках разница мала — при десятке элементов линейный и бинарный поиск различаются на единицы шагов.

Язык

Примеры на Python — запись границ и переполнение зависят от языка и типа чисел.

Сложность

Рост, а не секунды — O(…) показывает, как растёт число шагов, а не время в секундах.

Частые ошибки

• Применяют бинарный поиск к неотсортированному списку и получают «не найдено» для существующего элемента.
• Ошибаются на единицу в границах и получают бесконечный цикл или пропуск элемента.
• Считают середину как (низ + верх) / 2 в языках с ограниченными целыми числами.
• Сортируют список заново перед каждым поиском: тогда выигрыш бинарного поиска пропадает.
• Используют in и index на огромных отсортированных списках, хотя быстрее bisect.
• Путают поиск элемента в списке и поиск в интернете.

Короткий вывод

Линейный поиск работает везде, но медленно растёт вместе со списком. Бинарный поиск быстрее, но требует отсортированных данных и аккуратных границ. В Python для отсортированных списков берите bisect, а для случайных коротких — обычный in.