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

Вычисляемые данные: индекс (номер позиции) элемента, равного искомому (или ответ, что такого элемента нет).
Формулы метода: элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д. Единственное вычисление, которое производится на каждой итерации метода — вычисление среднего арифметического левого и правого индексов: mk=lk+rk2. Здесь и далее за lk,rk,mk обозначаются индексы левого конца, правого конца и середины рассматриваемого отрезка массива на k-ой итерации. Сначала поиск производится по всему массиву, поэтому l0=0,r0=n−1.


Схема реализации последовательного алгоритма

1. 
   Инициализируем концы отрезка концами всего массива: l0=0,r0=n−1.
   
2. 
   Если lk>rk, то поиск завершается как неуспешный (см. о возвращаемом значении). Иначе находим позицию середины отрезка массива как целую часть от полусуммы позиций его концов: mk=[lk+rk2].
   
3. 
   Если xmk
4. 
   Если xmk>A, то устанавливаем rk:=mk−1 и идём к шагу 2.
   
5. 
   Если xmk=A, то поиск закончен и значение найдено, возвращаем номер позиции mk.
   

Сложность алгоритма
Количество итераций K в худшем случае^[7] (когда элемент не найден, или находится на последнем шагу) легко оценить, если количество элементов в массиве n=2m−1. После первого повторения цикла, если A не был найден, размер области поиска становится равным n−12, то есть опять является числом того же вида — степень двойки минус единица. После i повторений, если A всё ещё не найден, в области поиска останется 2m−i−1 элементов. Значит, после m−1 повторения останется один элемент. После этого цикл повторится ещё один раз и работа будет закончена. Таким образом, общее число повторений цикла равно K=m=log2(n+1). Нетрудно показать, что в общем случае (когда n произвольное) число повторений будет равно ближайшему целому сверху к числу log2(n+1), то есть K=⌈log2(n+1)⌉.
В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива. Для вида n=2m−1 : K=1n∑log2(n+1)−1i=0i2i=[log2(n+1)]+2n−2, в общем виде отличается от формулы не более, чем на 0,5. В лучшем же случае (когда элемент сразу найден) — K=1.
Таким образом, алгоритм обладает логарифмической временной сложностью по данным и даже последовательная реализация достаточно быстра и, в принципе, не нуждается в распараллеливании.

Бинарный поиск требует предобработку (сортировку, сложность которой не менее O(nlog2n)) и особенно полезен, если массив большой и поиск проводится неоднократное (точнее, более, чем порядка O(log2n)) число раз.