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

Последовательный поиск не является самым эффективным алгоритмом поиска. Например, человеку нужно найти в русско-английском словаре перевод слова на английский язык. Если он будет искать его с помощью алгоритма последовательного поиска (просматривая все слова подряд), то он потратит очень много времени. На самом же деле интуитивно человек действует совсем по-другому. Запишем инструкцию для поиска перевода слова в словаре. При этом будем считать, что словарь не имеет вырезанных сбоку букв русского алфавита, а нумерация страниц может быть и затерта в результате частого использования словаря.

Исполнитель данного алгоритма — человек, имеющий две руки, умеющий читать и сравнивать два слова на предмет, какое из них раньше стоит в словаре. Итак, алгоритм:

1. Если в словаре больше одного разворота страниц, то открыть словарь примерно посередине, иначе перейти на шаг 6.

2. Сравнить самое первое слово на развороте с искомым словом.

3. Если искомое слово стоит раньше, чем первое слово на развороте, то заложить рукой открытую страницу и часть словаря от начала до заложенной страницы считать новым словарем. Перейти к шагу 1.

4. Если искомое слово стоит позже, чем первое слово на развороте, то сравнить последнее слово на развороте с искомым словом.

5. Если искомое слово стоит позже, чем последнее слово на развороте, то заложить рукой открытую страницу и часть словаря от заложенной страницы до конца считать новым словарем. Перейти к шагу 1.

6. Просмотреть все от первого до последнего слова на развороте. Если искомое слово найдено – алгоритм окончен успешно, иначе – искомого слова в словаре нет.

Скачать текст программы

Поиск слова в словаре наиболее приближен к алгоритму бинарного (двоичного) поиска, который также называют логарифмическим поиском, или методом деления пополам (дихотомией). Этот алгоритм достаточно эффективен, но использовать его можно только в случае, когда данные упорядочены. В этом алгоритме мы используем сравнение искомого элемента с серединным элементом и с помощью результата этого сравнения устанавливаем, в какой части данных находится искомый элемент.

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

Задача	Бинарный поиск	Последовательный поиск
Мы по телефону получаем количество проголосовавших на каждом участке, и нам надо найти участок, на котором проголосовало N человек	НЕТ	ДА
Человек ищет нужный ему номер дома на улице	НЕТ	ДА
В словаре ищем перевод нужного слова	ДА	НЕТ

Основная идея бинарного поиска довольно проста, но детали нетривиальны, и правильно написать работающий алгоритм удается далеко не с первого раза. В одной из наиболее популярных реализаций этого алгоритма используется два указателя (l и u), соответствующих нижней и верхней границам поиска. С помощью этого алгоритма ищется элемент k в упорядоченном по возрастанию массиве a, содержащем n элементов:

1. Начальная установка l = 1, u = n.

2. Если u < l, то алгоритм окончен неудачно, иначе найти середину интервала [l; u]. В этот момент мы знаем, что если k есть в массиве, то выполняются неравенства a_l ≤ k ≤ a_u. Установить i = [(l + u) / 2]. Теперь i указывает примерно на середину рассматриваемой части массива.

3. Если k > a_i, то перейти к шагу 4, если k > a_i, то перейти к шагу 5, если k = a_i, алгоритм окончен удачно.

4. Установить u = i – 1 и перейти к шагу 2.

5. Установить l = i + 1 и перейти к шагу 2.

Шаг 3 алгоритма бинарного поиска выполняется примерно log₂n раз, то есть данный алгоритм имеет логарифмическую сложность по числу сравнений.