Двоичный (бинарный) поиск в отсортированном массиве

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

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

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

Как работает алгоритм

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

1. находим середину: сер = (лево + право) / 2 (деление нацело);
2. если элемент в середине равен искомому — ответ найден;
3. если средний элемент больше искомого — ищем в левой половине (право = сер - 1);
4. если меньше — ищем в правой половине (лево = сер + 1).

Поиск продолжается, пока лево не превысит право — тогда элемента в массиве нет. Идея похожа на угадывание задуманного числа: спрашивая «больше или меньше середины?», мы каждым вопросом отсекаем половину оставшихся вариантов и очень быстро приближаемся к ответу.

Запись алгоритма

На школьном алгоритмическом языке двоичный поиск можно записать так:

лево := 1
право := n
пока лево <= право:
  сер := (лево + право) div 2
  если A[сер] = x то
    нашли, выход
  иначе если A[сер] < x то
    лево := сер + 1
  иначе
    право := сер - 1

Разбор примера

Ищем число 23 в массиве из 8 элементов: [3, 7, 11, 15, 19, 23, 27, 31]. Индексы от 1 до 8.

Понадобилось всего 2 сравнения вместо 6 при обычном переборе.

Сравнение с линейным поиском

Линейный поиск проверяет элементы по одному, и в худшем случае ему нужно n сравнений. Двоичный поиск каждый раз уменьшает зону поиска вдвое, поэтому ему достаточно примерно log₂(n) сравнений. Разница огромна: чтобы найти слово в словаре из миллиона слов, линейный перебор может потребовать миллион проверок, а двоичный поиск справится примерно за двадцать. Именно поэтому большие отсортированные данные ищут только двоичным методом.

Частые ошибки. Двоичный поиск применим только к отсортированным данным. Не забывайте сдвигать границу на единицу (сер - 1 или сер + 1), иначе возможно зацикливание. Условие выхода — лево > право, а не равенство.

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

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