Занятие №5 Класс алгоритмических методов «разделяй и властвуй»

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

Чаще всего бинарный поиск (бинпоиск) используют, чтобы найти элемент в отсортированном массиве. Мы начинаем искать с середины массива. Если находим то, что нужно, или если больше нечего рассматривать, мы останавливаемся. В противном случае мы решаем, в каком направлении — вправо или влево от середины — мы должны продолжить поиск. Так как пространство поиска после каждой проверки делится на два, то время выполнения алгоритма — O(log n).

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

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

Метод двоичного поиска используется в качестве быстрого варианта поиска в заранее отсортированном массиве. Получил распространение благодаря как наименьшей из возможных высоте алгоритма, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.

Основная идея заключается в дроблении массива на половины и дальнейшем рекурсивном поиске в одной из них.
Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году. Первое время все реализации работали только для массивов длины 2k−1, пока в 1960 году Деррек Генри Лемер не опубликовал первый алгоритм, работающий на массивах произвольной длины. В 1962 году Германн Боттенбрух представил реализацию метода на Алгол-60, в которой сравнение было помещено в конец, увеличивая количество итераций алгоритма на один, но уменьшая число сравнений до одного на итерацию. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading, a technique used to speed up binary searches in multiple arrays.
Исходные данные: одномерный массив n чисел xi,i=0..n−1, упорядоченный по возрастанию (точнее — неубыванию) или убыванию (точнее — невозрастанию), а также число A, которое нужно найти в этом массиве.