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

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

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

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

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

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. Забывают вернуть «не найдено», когда элемента нет.

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

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