Линейный и двоичный поиск

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

Поиск — это определение, есть ли в массиве заданный элемент, и если есть, то на каком месте. Это одна из самых частых операций в программировании. Два основных метода — линейный (последовательный) поиск и двоичный (бинарный) поиск.

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

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

nayden = -1
for i in range(n):
if a[i] == x:
nayden = i
break

Переменная nayden хранит индекс найденного элемента или -1, если элемента нет. Оператор break прекращает поиск после первого совпадения.

Двоичный поиск

Работает только в упорядоченном массиве, зато гораздо быстрее. Идея: сравнить искомое со средним элементом. Если он меньше — искать в левой половине, если больше — в правой. На каждом шаге область поиска уменьшается вдвое.

lo, hi = 0, n-1
while lo <= hi:
m = (lo + hi) // 2
if a[m] == x: ...найден
elif a[m] < x: lo = m + 1
else: hi = m - 1

Сравнение методов

Свойство	Линейный	Двоичный
Массив	любой	упорядоченный
Шагов в худшем случае	n	около log₂ n
Простота	очень простой	сложнее

Для массива из миллиона элементов линейный поиск в худшем случае сделает миллион сравнений, а двоичный — около двадцати. Разница огромна, но за неё платят требованием упорядоченности.

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

Разберём поиск числа 7 в упорядоченном массиве 1 3 5 7 9 11. Средний элемент (индекс 2) равен 5; искомое больше, значит ищем правее, сдвигаем lo на индекс 3. Теперь область — 7 9 11, средний элемент 9; искомое меньше, сдвигаем hi влево. Остаётся элемент 7 — найден за три сравнения вместо четырёх при линейном переборе. Чем больше массив, тем заметнее выигрыш.

Когда что выбирать

Если массив небольшой или поиск выполняется один раз, проще линейный метод — он не требует предварительной сортировки. Если же по одному и тому же массиву ищут многократно, выгодно один раз отсортировать его и затем применять двоичный поиск. Затраты на сортировку окупаются множеством быстрых поисков. Этот выбор — пример того, как программист взвешивает разные характеристики алгоритмов.

Частые ошибки. Применение двоичного поиска к неотсортированному массиву даёт неверный результат. Бесконечный цикл при неправильном сдвиге границ lo и hi. Забывают вернуть «не найдено», когда элемента нет.

Двоичный поиск с двумя воображаемыми границами

В отсортированном по неубыванию списке найдём первый элемент, не меньший key. Держим индексы left = −1 и right = len(a): слева от области всё меньше key, справа — не меньше. Границы воображаемые: обращаться к a[−1] и a[len(a)] для проверки этих условий нельзя.

def lower_bound(a, key):
    left, right = -1, len(a)
    while right - left > 1:
        mid = (left + right) // 2
        if a[mid] < key:
            left = mid
        else:
            right = mid
    return right

a = [2, 4, 4, 4, 9]
i = lower_bound(a, 4)
found = i < len(a) and a[i] == 4
print(i, found)  # 1 True

Результат функции — место вставки. Если все элементы меньше key, вернётся len(a); для пустого списка — 0. Наличие числа проверяется отдельно, прежде чем читать a[i]. Для первого элемента строго больше key замените проверку a[mid] < key на a[mid] ≤ key; разность двух границ даст число повторений.

Поиск в потоке без хранения всех чисел

При последовательном вводе с завершающим нулём сортировка не нужна. В следующем примере 0 — служебный маркер и не входит в данные; target выбирают ненулевым.

def in_stream(values, target):
    for value in values:
        if value == 0:
            return False
        if value == target:
            return True
    return False

print(in_stream([8, 3, 7, 0], 7))  # True
print(in_stream([8, 0, 7], 7))     # False

Поток может быть итератором: функция не создаёт из него список и использует постоянную дополнительную память. Чтение прекращается сразу после совпадения или маркера. Если по условию требуется прочитать поток целиком, например для обработки последующих данных, ранний выход нужно заменить накоплением флага.

Бинарный поиск требует упорядоченного набора с доступом по индексу; поток обычно просматривают линейно. Это разные ограничения входа, а не два взаимозаменяемых фрагмента программы.

Справочные материалы: Задача поиска — исходная тема; Задача поиска — исходная тема. Связанные уроки: Поиск в массиве, Трассировка алгоритма по шагам.

Первоисточники: Python: bisect и границы вставки.

Кратко о главном

• Линейный поиск перебирает все элементы подряд, годится для любого массива.
• Двоичный поиск делит область вдвое, нужен упорядоченный массив.
• Линейный — до n шагов, двоичный — около log₂ n.
• Двоичный поиск намного быстрее на больших данных.