Уровень алгоритма

Двоичный поиск: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(викификация)
Строка 20: Строка 20:
 
[[Файл:Binary_search_into_array_-_example.svg|thumb|right|Рисунок 1. Поиск элемента 4 в массиве]]
 
[[Файл:Binary_search_into_array_-_example.svg|thumb|right|Рисунок 1. Поиск элемента 4 в массиве]]
  
Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году.<ref name="knuth">Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.</ref> Первое время все реализации работали только для массивов длины <math>2^k-1</math>, пока в 1960 году Деррек Генри Лемер не опубликовал первый алгоритм, работающий на массивах произвольной длины.<ref>Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10. pp. 180–181. doi:10.1090/psapm/010.</ref> В 1962 году Германн Боттенбрух представил реализацию метода на Алгол-60, в которой сравнение было помещено в конец, увеличивая количество итераций алгоритма на один, но уменьшая число сравнений до одного на итерацию.<ref>Bottenbruch, Hermann (1962). "Structure and Use of ALGOL 60". Journal of the ACM 9 (2): 161–211. Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading, a technique used to speed up binary searches in multiple arrays.[18][40][41]
+
Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году.<ref name="knuth">Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.</ref> Первое время все реализации работали только для массивов длины <math>2^k-1</math>, пока в 1960 году Деррек Генри Лемер не опубликовал первый алгоритм, работающий на массивах произвольной длины.<ref>Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10. pp. 180—181. doi:10.1090/psapm/010.</ref> В 1962 году Германн Боттенбрух представил реализацию метода на Алгол-60, в которой сравнение было помещено в конец, увеличивая количество итераций алгоритма на один, но уменьшая число сравнений до одного на итерацию.<ref>Bottenbruch, Hermann (1962). «Structure and Use of ALGOL 60». Journal of the ACM 9 (2): 161—211. Procedure is described at p. 214 (§ 43), titled «Program for Binary Search».</ref>. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading, a technique used to speed up binary searches in multiple arrays.[18][40][41]
  
Альтернативой служит [[метод линейного поиска]] (т.е. полного перебора), имеющий, соответственно, линейную вычислительную сложность (<math>O(n)</math>), однако работающий на произвольно упорядоченных массивах. Если сравнивать возможности применения обоих методов, то линейный поиск выгоднее применять 1) для поиска в коротких массивах; 2) когда требуется провести поиск небольшое число раз; 3) в потоковом случае. В отличие от него, бинарный поиск требует предобработку ([[Сортировка|сортировку]], сложность которой не менее <math>O(n \log_2 n)</math>) и особенно полезен, если массив большой и поиск проводится неоднократное (точнее, более, чем порядка <math>O(\log_2 n)</math>) число раз.
+
Альтернативой служит [[метод линейного поиска]] (то есть полного перебора), имеющий, соответственно, линейную вычислительную сложность (<math>O(n)</math>), однако работающий на произвольно упорядоченных массивах. Если сравнивать возможности применения обоих методов, то линейный поиск выгоднее применять 1) для поиска в коротких массивах; 2) когда требуется провести поиск небольшое число раз; 3) в потоковом случае. В отличие от него, бинарный поиск требует предобработку ([[Сортировка|сортировку]], сложность которой не менее <math>O(n \log_2 n)</math>) и особенно полезен, если массив большой и поиск проводится неоднократное (точнее, более, чем порядка <math>O(\log_2 n)</math>) число раз.
  
 
Метод позволяет различные обобщения и видоизменения:
 
Метод позволяет различные обобщения и видоизменения:
 
* [[Однородный двоичный поиск]], был представлен А. К. Чандрой в 1971 году Дональду Кнуту, который опубликовал его в своей монографии<ref name="knuth"/>.
 
* [[Однородный двоичный поиск]], был представлен А. К. Чандрой в 1971 году Дональду Кнуту, который опубликовал его в своей монографии<ref name="knuth"/>.
 
* [[Троичный поиск]], когда отрезок делится на три части. Применяется для поиска положения экстремума функции.
 
* [[Троичный поиск]], когда отрезок делится на три части. Применяется для поиска положения экстремума функции.
* [[Интерполирующий поиск]], делящий область поиска не пополам, а предсказывающий позицию искомого элемента на основе разницы значений. Работает быстрее, если элементы распределены достаточно равномерно - в среднем <math>O(\log \log n)</math>. В худшем случае, работает за <math>O(n)</math>).
+
* [[Интерполирующий поиск]], делящий область поиска не пополам, а предсказывающий позицию искомого элемента на основе разницы значений. Работает быстрее, если элементы распределены достаточно равномерно в среднем <math>O(\log \log n)</math>. В худшем случае, работает за <math>O(n)</math>).
* [[Дробный спуск]] ({{lang-en|fractional cascading}}), предложенный в 1986 году Бернаром Шазеллем и Леонидасом Дж. Гуйбасом, как техника ускорения бинарного поиска в многомерных массивах.<ref>Chazelle, Bernard; Liu, Ding (2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. pp. 322–329. doi:10.1145/380752.380818.</ref><ref>Chazelle, Bernard; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF). Algorithmica 1 (1): 133–162. doi:10.1007/BF01840440.</ref><ref>Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica 1 (1): 163–191, doi:10.1007/BF01840441</ref>.
+
* [[Дробный спуск]] ({{lang-en|fractional cascading}}), предложенный в 1986 году Бернаром Шазеллем и Леонидасом Дж. Гуйбасом, как техника ускорения бинарного поиска в многомерных массивах.<ref>Chazelle, Bernard; Liu, Ding (2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. pp. 322—329. doi:10.1145/380752.380818.</ref><ref>Chazelle, Bernard; Guibas, Leonidas J. (1986). «Fractional cascading: I. A data structuring technique» (PDF). Algorithmica 1 (1): 133—162. doi:10.1007/BF01840440.</ref><ref>Chazelle, Bernard; Guibas, Leonidas J. (1986), «Fractional cascading: II. Applications» (PDF), Algorithmica 1 (1): 163—191, doi:10.1007/BF01840441</ref>.
  
 
Вариации также могут касаться формата и сути вывода результата в отдельных случаях (см. [[#Особенности реализации последовательного алгоритма|варианты возврата при ненахождении]]).
 
Вариации также могут касаться формата и сути вывода результата в отдельных случаях (см. [[#Особенности реализации последовательного алгоритма|варианты возврата при ненахождении]]).
  
Очень близко к метод бинарного поиска по массиву стоит непрерывный аналог - [https://ru.wikipedia.org/wiki/Метод_бисекции метод бисекции] ([[метод деления пополам]]) нахождения корня непрерывной функции на заданном отрезке. Самое большое отличие заключается в вычислении значения функции вместо нахождения элемента массива по его индексу, а также использование действительных чисел в качестве аргумента в отличие от целых чисел для индексации элементов массива.
+
Очень близко к метод бинарного поиска по массиву стоит непрерывный аналог — [[ru-wikipedia:Метод_бисекции|метод бисекции]] ([[метод деления пополам]]) нахождения корня непрерывной функции на заданном отрезке. Самое большое отличие заключается в вычислении значения функции вместо нахождения элемента массива по его индексу, а также использование действительных чисел в качестве аргумента в отличие от целых чисел для индексации элементов массива.
  
По своему определению, алгоритм может быть записан в одной из двух основных форм - рекурсивной и итеративной. Поскольку вычислительное ядро в них одинаковое, но в рекурсивном есть дополнительная нагрузка по вызову функций и хранению их стека, в данной статье рассматривается только итеративная версия.
+
По своему определению, алгоритм может быть записан в одной из двух основных форм рекурсивной и итеративной. Поскольку вычислительное ядро в них одинаковое, но в рекурсивном есть дополнительная нагрузка по вызову функций и хранению их стека, в данной статье рассматривается только итеративная версия.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 
+
'''Исходные данные''': одномерный массив <math>n</math> чисел <math>x_i, i=0..n-1</math>, упорядоченный по возрастанию (точнее неубыванию) или убыванию (точнее невозрастанию), а также число <math>A</math>, которое нужно найти в этом массиве.
'''Исходные данные''': одномерный массив <math>n</math> чисел <math>x_i, i=0..n-1</math>, упорядоченный по возрастанию (точнее - неубыванию) или убыванию (точнее - невозрастанию), а также число <math>A</math>, которое нужно найти в этом массиве.
 
  
 
'''Вычисляемые данные''': индекс (номер позиции) элемента, равного искомому (или ответ, что такого элемента нет).
 
'''Вычисляемые данные''': индекс (номер позиции) элемента, равного искомому (или ответ, что такого элемента нет).
  
 
'''Формулы метода''': элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
 
'''Формулы метода''': элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
Единственное вычисление, которое производится на каждой итерации метода - вычисление среднего арифметического левого и правого индексов: <math>m_k=\frac{l_k+r_k}{2}</math>.
+
Единственное вычисление, которое производится на каждой итерации метода вычисление среднего арифметического левого и правого индексов: <math>m_k=\frac{l_k+r_k}{2}</math>.
 
Здесь и далее за <math>l_k, r_k, m_k</math> обозначаются индексы левого конца, правого конца и середины рассматриваемого отрезка массива на <math>k</math>-ой итерации. Сначала поиск производится по всему массиву, поэтому <math>l_0 = 0, r_0 = n-1</math>.
 
Здесь и далее за <math>l_k, r_k, m_k</math> обозначаются индексы левого конца, правого конца и середины рассматриваемого отрезка массива на <math>k</math>-ой итерации. Сначала поиск производится по всему массиву, поэтому <math>l_0 = 0, r_0 = n-1</math>.
  
Строка 59: Строка 58:
 
# Если <math>x_{m_k}=A</math>, то поиск закончен и значение найдено, возвращаем номер позиции <math>m_k</math>.
 
# Если <math>x_{m_k}=A</math>, то поиск закончен и значение найдено, возвращаем номер позиции <math>m_k</math>.
  
В рекурсивном варианте определяется функция, принимающая в числе прочих параметров индексы концов отрезка массива, на котором идёт текущий поиск, а операция "идём к шагу 2" означает вызов той же функции поиска с другими индексами концов отрезка.
+
В рекурсивном варианте определяется функция, принимающая в числе прочих параметров индексы концов отрезка массива, на котором идёт текущий поиск, а операция «идём к шагу означает вызов той же функции поиска с другими индексами концов отрезка.
  
 
В итеративном варианте пп. 2-5 обёрнуты в бесконечный цикл, выход из которого возможен либо в п. 2 (как неуспешный), либо в п. 5, когда значение найдено.
 
В итеративном варианте пп. 2-5 обёрнуты в бесконечный цикл, выход из которого возможен либо в п. 2 (как неуспешный), либо в п. 5, когда значение найдено.
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
Количество итераций <math>K</math> в худшем случае<ref>[http://a-urusov2011.narod.ru/index/0-8 Асимптотические оценки]</ref> (когда элемент не найден, или находится на последнем шагу) легко оценить, если количество элементов в массиве <math>n=2^m-1</math>. После первого повторения цикла, если <math>A</math> не был найден, размер области поиска становится равным <math>\frac{n-1}{2}</math>, т.е. опять является числом того же вида степень двойки минус единица. После <math>i</math> повторений, если <math>A</math> всё ещё не найден, в области поиска останется <math>2^{m-i-1}</math> элементов. Значит, после <math>m-1</math> повторения останется один элемент. После этого цикл повторится ещё один раз и работа будет закончена. Таким образом, общее число повторений цикла равно <math>K = m = \log_2 (n + 1)</math>.
+
Количество итераций <math>K</math> в худшем случае<ref>[http://a-urusov2011.narod.ru/index/0-8 Асимптотические оценки]</ref> (когда элемент не найден, или находится на последнем шагу) легко оценить, если количество элементов в массиве <math>n=2^m-1</math>. После первого повторения цикла, если <math>A</math> не был найден, размер области поиска становится равным <math>\frac{n-1}{2}</math>, то есть опять является числом того же вида степень двойки минус единица. После <math>i</math> повторений, если <math>A</math> всё ещё не найден, в области поиска останется <math>2^{m-i-1}</math> элементов. Значит, после <math>m-1</math> повторения останется один элемент. После этого цикл повторится ещё один раз и работа будет закончена. Таким образом, общее число повторений цикла равно <math>K = m = \log_2 (n + 1)</math>.
Нетрудно показать, что в общем случае (когда <math>n</math> произвольное) число повторений будет равно ближайшему целому сверху к числу <math>\log_2 (n + 1)</math>, т.е. <math>K=\lceil\log_2 (n + 1)\rceil</math>.
+
Нетрудно показать, что в общем случае (когда <math>n</math> произвольное) число повторений будет равно ближайшему целому сверху к числу <math>\log_2 (n + 1)</math>, то есть <math>K=\lceil\log_2 (n + 1)\rceil</math>.
  
 
В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива. Для вида <math>n=2^m-1</math> : <math>K=\frac{1}{n}\sum_{i=0}^{\log_2 (n+1)
 
В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива. Для вида <math>n=2^m-1</math> : <math>K=\frac{1}{n}\sum_{i=0}^{\log_2 (n+1)
-1} i\, 2^i=[\log_2 (n+1)] +\frac{2}{n}-2</math>, в общем виде отличается от формулы не более, чем на 0,5. В лучшем же случае (когда элемент сразу найден) - <math>K=1</math>.
+
-1} i\, 2^i=[\log_2 (n+1)] +\frac{2}{n}-2</math>, в общем виде отличается от формулы не более, чем на 0,5. В лучшем же случае (когда элемент сразу найден) <math>K=1</math>.
  
 
Таким образом, алгоритм обладает логарифмической временной сложностью по данным и даже последовательная реализация достаточно быстра и, в принципе, не нуждается в распараллеливании.
 
Таким образом, алгоритм обладает логарифмической временной сложностью по данным и даже последовательная реализация достаточно быстра и, в принципе, не нуждается в распараллеливании.
Строка 75: Строка 74:
 
Граф алгоритма является параметризованным (зависит от размера массива) и недетерминированным (в смысле, что порядок вычислений зависит от начальных данных).
 
Граф алгоритма является параметризованным (зависит от размера массива) и недетерминированным (в смысле, что порядок вычислений зависит от начальных данных).
  
На рисунке ниже изображён граф алгоритма для <math>K = 9</math>. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "сравнить значение массива на позиции <math>m_k</math> с искомым элементом <math>A</math> и обновить значение пары <math>(l_k, r_k)</math>".
+
На рисунке ниже изображён граф алгоритма для <math>K = 9</math>. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op операция «сравнить значение массива на позиции <math>m_k</math> с искомым элементом <math>A</math> и обновить значение пары <math>(l_k, r_k)</math>».
  
[[file:Basic sequental algorithm graph.png|center|thumb|800px|Рисунок 2. Операции в алгоритме бинарного поиска: последовательная версия]]
+
[[Файл:Basic sequental algorithm graph.png|center|thumb|800px|Рисунок 2. Операции в алгоритме бинарного поиска: последовательная версия]]
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
Сам по себе алгоритм не может быть распараллелен, т.к. его информационный граф имеет линейный вид. Его [[Глоссарий#Ярусно-параллельная форма графа алгоритма|ярусно-параллельная форма (ЯПФ)]] — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет порядка <math>K=\log_2 n</math>, содержа <math>K</math> операций умножения плюс <math>K</math> операций сложения плюс <math>K</math> операций сравнения. В таком виде алгоритм должен быть отнесён к алгоритмам логарифмической сложности по высоте параллельной формы. Ширина параллельной формы равна 1, что даёт нам постоянную сложность по ширине параллельной формы.
+
Сам по себе алгоритм не может быть распараллелен, так как его информационный граф имеет линейный вид. Его [[Глоссарий#Ярусно-параллельная форма графа алгоритма|ярусно-параллельная форма (ЯПФ)]] — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет порядка <math>K=\log_2 n</math>, содержа <math>K</math> операций умножения плюс <math>K</math> операций сложения плюс <math>K</math> операций сравнения. В таком виде алгоритм должен быть отнесён к алгоритмам логарифмической сложности по высоте параллельной формы. Ширина параллельной формы равна 1, что даёт нам постоянную сложность по ширине параллельной формы.
  
Однако существует очевидная [[p-арный поиск|модификация алгоритма]], которая позволяет использовать любое наперёд заданное число процессоров <math>p</math> - деление не на 2 части, а на <math>p+1</math> часть. При этом вычисления всех новых узлов, а также сравнение значений в них с <math>A</math> можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка <math>K=\log_{p+1} n</math>.
+
Однако существует очевидная [[p-арный поиск|модификация алгоритма]], которая позволяет использовать любое наперёд заданное число процессоров <math>p</math> деление не на 2 части, а на <math>p+1</math> часть. При этом вычисления всех новых узлов, а также сравнение значений в них с <math>A</math> можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка <math>K=\log_{p+1} n</math>.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
 
 
Входные данные: массив <math>x</math> (элементы <math>x_i</math>). Число <math>A</math>.
 
Входные данные: массив <math>x</math> (элементы <math>x_i</math>). Число <math>A</math>.
  
 
Дополнительные ограничения: массив упорядочен.
 
Дополнительные ограничения: массив упорядочен.
  
Объём входных данных: <math>n</math>.  
+
Объём входных данных: <math>n</math>.
  
 
Выходные данные: индекс элемента <math>A</math> в массиве, если он есть.
 
Выходные данные: индекс элемента <math>A</math> в массиве, если он есть.
Строка 101: Строка 99:
 
[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма порядка <math>\frac{\log_2 n}{n}</math>.
 
[[глоссарий#Вычислительная мощность|''Вычислительная мощность'']] алгоритма порядка <math>\frac{\log_2 n}{n}</math>.
  
Алгоритм абсолютно [[глоссарий#Устойчивость|''устойчив'']], т.к. действия производятся только над целыми числами, и поэтому погрешность всегда равна 0.
+
Алгоритм абсолютно [[глоссарий#Устойчивость|''устойчив'']], так как действия производятся только над целыми числами, и поэтому погрешность всегда равна 0.
  
Алгоритм [[глоссарий#Детерминированность|''недетерминирован'']] в смысле структуры вычислительного процесса, т.к. число итераций, а значит и число операций, зависят от входных данных, в частности от искомого значения <math>A</math>. Однако он детерминирован в смысле, что выдаёт всегда одинаковый результат при одинаковых входных данных.
+
Алгоритм [[глоссарий#Детерминированность|''недетерминирован'']] в смысле структуры вычислительного процесса, так как число итераций, а значит и число операций, зависят от входных данных, в частности от искомого значения <math>A</math>. Однако он детерминирован в смысле, что выдаёт всегда одинаковый результат при одинаковых входных данных.
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
Строка 126: Строка 124:
  
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
Обычно в качестве ответа выводят -1, если число не найдено.
+
Обычно в качестве ответа выводят −1, если число не найдено.
  
 
Другие возможные варианты в данной ситуации (выбор зависит от того, как и где будет использоваться метод поиска как базовая единица)<ref>[https://habrahabr.ru/post/146228/ Я не могу написать бинарный поиск]</ref>:
 
Другие возможные варианты в данной ситуации (выбор зависит от того, как и где будет использоваться метод поиска как базовая единица)<ref>[https://habrahabr.ru/post/146228/ Я не могу написать бинарный поиск]</ref>:
# "магическое число" - то, которое заведомо не получится в качестве результата, если <math>A</math> найдено. В частности, можно возвращать <math>-(l_k+1)</math>, где <math>k</math> - последняя итерация перед нарушением условия <math>l_k < r_k</math>, передавая таким образом информации о месте, где могло бы находиться <math>A</math>. Эту информацию можно использовать, в частности, для дальнейшей вставки нового объекта на нужное место в массиве, чтобы оставить его упорядоченным.
+
# «магическое число» — то, которое заведомо не получится в качестве результата, если <math>A</math> найдено. В частности, можно возвращать <math>-(l_k+1)</math>, где <math>k</math> последняя итерация перед нарушением условия <math>l_k < r_k</math>, передавая таким образом информации о месте, где могло бы находиться <math>A</math>. Эту информацию можно использовать, в частности, для дальнейшей вставки нового объекта на нужное место в массиве, чтобы оставить его упорядоченным.
# специальная константа. Её наличие определяется языком программирования. Например, это может быть null в C# (тогда потребуется использовать тип "int?" в качестве типа результата вместо простого "int"), или ... в Python'е
+
# специальная константа. Её наличие определяется языком программирования. Например, это может быть null в C# (тогда потребуется использовать тип «int?» в качестве типа результата вместо простого «int»), или в Python’е
 
# кинуть исключение. Это используется, когда элемент должен был найтись, и дальнейшая работа невозможна, если его не нашлось.
 
# кинуть исключение. Это используется, когда элемент должен был найтись, и дальнейшая работа невозможна, если его не нашлось.
  
 
==== Частые ошибки при реализации ====
 
==== Частые ошибки при реализации ====
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек, на которые нужно обратить внимание<ref>[https://habrahabr.ru/post/91605/ Только 10% программистов способны написать двоичный поиск]</ref>:
+
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек, на которые нужно обратить внимание<ref>[https://habrahabr.ru/post/91605/ Только 10 % программистов способны написать двоичный поиск]</ref>:
 
* Что будет, если <code>first</code> и <code>last</code> по отдельности умещаются в свой тип, а <code>first+last</code> — нет?<ref name="joshua">[http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken] // Joshua Bloch, Google Research; перевод — [http://habrahabr.ru/post/203398/ Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка]</ref> Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
 
* Что будет, если <code>first</code> и <code>last</code> по отдельности умещаются в свой тип, а <code>first+last</code> — нет?<ref name="joshua">[http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken] // Joshua Bloch, Google Research; перевод — [http://habrahabr.ru/post/203398/ Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка]</ref> Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
 
** Использовать код <code>first + (last - first) / 2</code>, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).
 
** Использовать код <code>first + (last - first) / 2</code>, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).
*** Если <code>first</code> и <code>last</code> — указатели или [https://ru.wikipedia.org/wiki/Итератор итераторы], такой код единственно правильный. Преобразование в <code>uintptr_t</code> и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
+
*** Если <code>first</code> и <code>last</code> — указатели или [[ru-wikipedia:Итератор|итераторы]], такой код единственно правильный. Преобразование в <code>uintptr_t</code> и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
 
** Если <code>first</code> и <code>last</code> — типы со знаком, провести расчёт в беззнаковом типе: <code>((unsigned)first + (unsigned)last) / 2</code>. В [[Java]] соответственно: <code>(first + last) >>> 1</code>.
 
** Если <code>first</code> и <code>last</code> — типы со знаком, провести расчёт в беззнаковом типе: <code>((unsigned)first + (unsigned)last) / 2</code>. В [[Java]] соответственно: <code>(first + last) >>> 1</code>.
** Написать расчёт на ассемблере, с использованием [https://ru.wikipedia.org/wiki/Флаг_переноса флага переноса]. Что-то наподобие <code>add eax, b; rcr eax, 1</code>. А вот [https://ru.wikipedia.org/wiki/Длинная_арифметика длинные типы] использовать нецелесообразно, <code>first + (last - first) / 2</code> быстрее.
+
** Написать расчёт на ассемблере, с использованием [[ru-wikipedia:Флаг_переноса|флага переноса]]. Что-то наподобие <code>add eax, b; rcr eax, 1</code>. А вот [[ru-wikipedia:Длинная_арифметика|длинные типы]] использовать нецелесообразно, <code>first + (last - first) / 2</code> быстрее.
* В двоичном поиске часты [https://ru.wikipedia.org/wiki/Ошибка_на_единицу ошибки на единицу]. Поэтому важно протестировать такие случаи: пустой массив (<code>n=0</code>), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
+
* В двоичном поиске часты [[ru-wikipedia:Ошибка_на_единицу|ошибки на единицу]]. Поэтому важно протестировать такие случаи: пустой массив (<code>n=0</code>), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
* Иногда требуется, чтобы, если <code>x</code> в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не <code>x</code>, а следующий за ним элемент).<ref>В [https://ru.wikipedia.org/wiki/C%2B%2B C++] <code>std::lower_bound</code> находит первое вхождение <code>x</code>, а <code>std::upper_bound</code> — элемент, следующий за <code>x</code>.</ref>
+
* Иногда требуется, чтобы, если <code>x</code> в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не <code>x</code>, а следующий за ним элемент).<ref>В [[ru-wikipedia:C%2B%2B|C++]] <code>std::lower_bound</code> находит первое вхождение <code>x</code>, а <code>std::upper_bound</code> — элемент, следующий за <code>x</code>.</ref>
  
 
Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.
 
Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>.
 +
 
=== Локальность данных и вычислений ===
 
=== Локальность данных и вычислений ===
[[Глоссарий#Пространственная локальность|Пространственная локальность]] достаточно плохая - начальные обращения в память гарантированно далеки друг от друга. Однако расстояние с номером итерации экспоненциально уменьшается и в конце есть надежда на использование преимуществ локальности обращений.
+
[[Глоссарий#Пространственная локальность|Пространственная локальность]] достаточно плохая начальные обращения в память гарантированно далеки друг от друга. Однако расстояние с номером итерации экспоненциально уменьшается и в конце есть надежда на использование преимуществ локальности обращений.
  
[[Глоссарий#Временная локальность|Временная локальность]] ещё хуже - один и тот же элемент массива никогда не требуется дважды.
+
[[Глоссарий#Временная локальность|Временная локальность]] ещё хуже один и тот же элемент массива никогда не требуется дважды.
  
 
==== Локальность реализации алгоритма ====
 
==== Локальность реализации алгоритма ====
 +
 
===== Структура обращений в память и качественная оценка локальности =====
 
===== Структура обращений в память и качественная оценка локальности =====
[[File:binary search memory access.png|500px|Рисунок 3. Реализация двоичного поиска. Общий профиль обращений в память.|thumb|center]]
+
[[Файл:binary search memory access.png|500px|Рисунок 3. Реализация двоичного поиска. Общий профиль обращений в память.|thumb|center]]
 
На рис. 3 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.
 
На рис. 3 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.
  
Строка 159: Строка 159:
  
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Возможные способы и особенности параллельной реализации алгоритма ===
Можно придумать модификацию алгоритма - [[p-арный поиск]], которая позволит использовать любое наперёд заданное число процессоров <math>p</math> - для этого надо делить область поиска не на 2 части, а на <math>p+1</math> часть. При этом вычисления всех новых узлов, а также сравнение значений в них с <math>A</math> можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка <math>K=\log_{p+1} n</math>.
+
Можно придумать модификацию алгоритма [[p-арный поиск]], которая позволит использовать любое наперёд заданное число процессоров <math>p</math> для этого надо делить область поиска не на 2 части, а на <math>p+1</math> часть. При этом вычисления всех новых узлов, а также сравнение значений в них с <math>A</math> можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка <math>K=\log_{p+1} n</math>.
  
 
Однако при этом потребуется предусмотреть обмен результатами сравнения своей точки деления на каждом процессоре для определения искомого интервала для следующей итерации. Это потребует минимум одной коллективной операции обмена, что ставит под сомнение эффективность распараллеливания.
 
Однако при этом потребуется предусмотреть обмен результатами сравнения своей точки деления на каждом процессоре для определения искомого интервала для следующей итерации. Это потребует минимум одной коллективной операции обмена, что ставит под сомнение эффективность распараллеливания.
  
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 +
 
==== Масштабируемость алгоритма ====
 
==== Масштабируемость алгоритма ====
  
 
==== Масштабируемость реализации алгоритма ====
 
==== Масштабируемость реализации алгоритма ====
 +
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
Использовать алгоритм в любой реализации для архитектур с разделённой памятью смысла не имеет - из-за нелокального доступа к исходным данным и малого количества вычислительных операций даже в параллельной модификации выигрыш будет съедаться коммуникациями.
+
Использовать алгоритм в любой реализации для архитектур с разделённой памятью смысла не имеет из-за нелокального доступа к исходным данным и малого количества вычислительных операций даже в параллельной модификации выигрыш будет съедаться коммуникациями.
  
 
Применение систем с общей памятью с помощью OpenMP теоретически имеет смысл, однако для получения хоть какого-то ускорения требуется выполнение нескольких условий:
 
Применение систем с общей памятью с помощью OpenMP теоретически имеет смысл, однако для получения хоть какого-то ускорения требуется выполнение нескольких условий:
Строка 177: Строка 179:
  
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
# В стандартной библиотеке языка C есть функция <code>bsearch()</code>, которая обычно реализована с помощью бинарного поиска (однако стандарт не гарантирует этого)<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html "bsearch – binary search a sorted table".] The Open Group Base Specifications (7th ed.). The Open Group. 2013</ref>
+
# В стандартной библиотеке языка C есть функция <code>bsearch()</code>, которая обычно реализована с помощью бинарного поиска (однако стандарт не гарантирует этого)<ref>[http://pubs.opengroup.org/onlinepubs/9699919799/functions/bsearch.html «bsearch — binary search a sorted table».] The Open Group Base Specifications (7th ed.). The Open Group. 2013</ref>
# Встроенные в C++ функции: <code>std::lower_bound</code> находит первое вхождение <math>A</math>, <code>std::upper_bound</code> возвращает индекс элемента за всеми <math>A</math>. Есть также <code>std::binary_search()</code> и <code>std::equal_range()</code>.<ref>Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2. §32.6.1 ("Binary Search")</ref>
+
# Встроенные в C++ функции: <code>std::lower_bound</code> находит первое вхождение <math>A</math>, <code>std::upper_bound</code> возвращает индекс элемента за всеми <math>A</math>. Есть также <code>std::binary_search()</code> и <code>std::equal_range()</code>.<ref>Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2. § 32.6.1 («Binary Search»)</ref>
# В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
+
# В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
# Microsoft's .NET Framework 2.0 предлагает статические функции-дженерики двоичного поиска в своей коллекции базовых классов. Например, метод класса System.Array's  <code>BinarySearch<T>(T[] array, T value)</code>.<ref>[https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx "List<T>.BinarySearch Method (T)"]. Microsoft Developer Network.</ref>
+
# Microsoft’s .NET Framework 2.0 предлагает статические функции-дженерики двоичного поиска в своей коллекции базовых классов. Например, метод класса System.Array’s <code>BinarySearch<T>(T[] array, T value)</code>.<ref>[https://msdn.microsoft.com/en-us/library/w4e7fxsh%28v=vs.110%29.aspx «List<T>.BinarySearch Method (T)»]. Microsoft Developer Network.</ref>
# В Python есть модуль <code>bisect</code><ref>[https://docs.python.org/2/library/bisect.html#module-bisect "8.5. bisect — Array bisection algorithm"]. The Python Standard Library. Python Software Foundation</ref>
+
# В Python есть модуль <code>bisect</code><ref>[https://docs.python.org/2/library/bisect.html#module-bisect «8.5. bisect — Array bisection algorithm»]. The Python Standard Library. Python Software Foundation</ref>
  
 
== См. также ==
 
== См. также ==
Строка 189: Строка 191:
  
 
== Литература ==
 
== Литература ==
<references />
+
{{примечания}}
* Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180-183. — ISBN 5-8459-0987-2.
+
* Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180—183. — ISBN 5-8459-0987-2.
 
* Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
 
* Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
 
* Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
 
* Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
Строка 197: Строка 199:
 
* Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
 
* Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
 
* Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
* Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
+
* Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
 
* Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
 
* Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
 
* Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
 
* Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
 
* Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
 
* Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.
  
== Внешние ссылки ==
+
== Ссылки ==
* [https://ru.wikipedia.org/wiki/Двоичный_поиск Метод двоичного поиска] в Википедии
+
* [[ru-wikipedia:Двоичный_поиск|Метод двоичного поиска]] в Википедии
 
* [http://algolist.manual.ru/search/bin_search.php Алгоритм] в библиотеке алгоритмов Algolist.
 
* [http://algolist.manual.ru/search/bin_search.php Алгоритм] в библиотеке алгоритмов Algolist.
 
* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике
 
* [https://ru.wikibooks.org/wiki/Реализации_алгоритмов/Двоичный_поиск Реализации алгоритма] в Викиучебнике

Версия 16:05, 8 июля 2016


Бинарный поиск
Последовательный алгоритм
Последовательная сложность [math]\log_2 n[/math] (в худшем и среднем случаях)
Объём входных данных упорядоченный массив длины [math]n[/math], число [math]A[/math]
Объём выходных данных индекc элемента
Параллельный алгоритм
Высота ярусно-параллельной формы [math]\log_2 n[/math]
Ширина ярусно-параллельной формы 1

Основные авторы описания: А. В. Чупин.

Синонимы названия метода: двоичный поиск, бинарный поиск, метод деления пополам, метод половинного деления, дихотомия.

Содержание

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Основная идея заключается в дроблении массива на половины и дальнейшем рекурсивном поиске в одной из них.

Рисунок 1. Поиск элемента 4 в массиве

Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году.[1] Первое время все реализации работали только для массивов длины [math]2^k-1[/math], пока в 1960 году Деррек Генри Лемер не опубликовал первый алгоритм, работающий на массивах произвольной длины.[2] В 1962 году Германн Боттенбрух представил реализацию метода на Алгол-60, в которой сравнение было помещено в конец, увеличивая количество итераций алгоритма на один, но уменьшая число сравнений до одного на итерацию.[3]. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading, a technique used to speed up binary searches in multiple arrays.[18][40][41]

Альтернативой служит метод линейного поиска (то есть полного перебора), имеющий, соответственно, линейную вычислительную сложность ([math]O(n)[/math]), однако работающий на произвольно упорядоченных массивах. Если сравнивать возможности применения обоих методов, то линейный поиск выгоднее применять 1) для поиска в коротких массивах; 2) когда требуется провести поиск небольшое число раз; 3) в потоковом случае. В отличие от него, бинарный поиск требует предобработку (сортировку, сложность которой не менее [math]O(n \log_2 n)[/math]) и особенно полезен, если массив большой и поиск проводится неоднократное (точнее, более, чем порядка [math]O(\log_2 n)[/math]) число раз.

Метод позволяет различные обобщения и видоизменения:

  • Однородный двоичный поиск, был представлен А. К. Чандрой в 1971 году Дональду Кнуту, который опубликовал его в своей монографии[1].
  • Троичный поиск, когда отрезок делится на три части. Применяется для поиска положения экстремума функции.
  • Интерполирующий поиск, делящий область поиска не пополам, а предсказывающий позицию искомого элемента на основе разницы значений. Работает быстрее, если элементы распределены достаточно равномерно — в среднем [math]O(\log \log n)[/math]. В худшем случае, работает за [math]O(n)[/math]).
  • Дробный спуск (англ. fractional cascading), предложенный в 1986 году Бернаром Шазеллем и Леонидасом Дж. Гуйбасом, как техника ускорения бинарного поиска в многомерных массивах.[4][5][6].

Вариации также могут касаться формата и сути вывода результата в отдельных случаях (см. варианты возврата при ненахождении).

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

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

1.2 Математическое описание алгоритма

Исходные данные: одномерный массив [math]n[/math] чисел [math]x_i, i=0..n-1[/math], упорядоченный по возрастанию (точнее — неубыванию) или убыванию (точнее — невозрастанию), а также число [math]A[/math], которое нужно найти в этом массиве.

Вычисляемые данные: индекс (номер позиции) элемента, равного искомому (или ответ, что такого элемента нет).

Формулы метода: элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д. Единственное вычисление, которое производится на каждой итерации метода — вычисление среднего арифметического левого и правого индексов: [math]m_k=\frac{l_k+r_k}{2}[/math]. Здесь и далее за [math]l_k, r_k, m_k[/math] обозначаются индексы левого конца, правого конца и середины рассматриваемого отрезка массива на [math]k[/math]-ой итерации. Сначала поиск производится по всему массиву, поэтому [math]l_0 = 0, r_0 = n-1[/math].

1.3 Вычислительное ядро алгоритма

Вычислительное ядро метода бинарного поиска состоит из операций сравнения и получения середины отрезка, которые рекуррентно выполняются для массивов всё меньшего размера. Количество сложений, умножений и сравнений прямо пропорционально количеству итераций, а оно не больше [math][ \log_2 n][/math].

1.4 Макроструктура алгоритма

По определению алгоритм состоит из рекурсивных вызовов самого себя для меньших массивов. Стандартные макрооперации не используются.

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

  1. Инициализируем концы отрезка концами всего массива: [math]l_0 = 0, r_0 = n-1[/math].
  2. Если [math]l_k\gt r_k[/math], то поиск завершается как неуспешный (см. о возвращаемом значении). Иначе находим позицию середины отрезка массива как целую часть от полусуммы позиций его концов: [math]m_k=\left[\frac{l_k+r_k}{2}\right][/math].
  3. Если [math]x_{m_k}\lt A[/math], то устанавливаем [math]l_k := m_k+1[/math] и идём к шагу 2.
  4. Если [math]x_{m_k}\gt A[/math], то устанавливаем [math]r_k := m_k-1[/math] и идём к шагу 2.
  5. Если [math]x_{m_k}=A[/math], то поиск закончен и значение найдено, возвращаем номер позиции [math]m_k[/math].

В рекурсивном варианте определяется функция, принимающая в числе прочих параметров индексы концов отрезка массива, на котором идёт текущий поиск, а операция «идём к шагу 2» означает вызов той же функции поиска с другими индексами концов отрезка.

В итеративном варианте пп. 2-5 обёрнуты в бесконечный цикл, выход из которого возможен либо в п. 2 (как неуспешный), либо в п. 5, когда значение найдено.

1.6 Последовательная сложность алгоритма

Количество итераций [math]K[/math] в худшем случае[7] (когда элемент не найден, или находится на последнем шагу) легко оценить, если количество элементов в массиве [math]n=2^m-1[/math]. После первого повторения цикла, если [math]A[/math] не был найден, размер области поиска становится равным [math]\frac{n-1}{2}[/math], то есть опять является числом того же вида — степень двойки минус единица. После [math]i[/math] повторений, если [math]A[/math] всё ещё не найден, в области поиска останется [math]2^{m-i-1}[/math] элементов. Значит, после [math]m-1[/math] повторения останется один элемент. После этого цикл повторится ещё один раз и работа будет закончена. Таким образом, общее число повторений цикла равно [math]K = m = \log_2 (n + 1)[/math]. Нетрудно показать, что в общем случае (когда [math]n[/math] произвольное) число повторений будет равно ближайшему целому сверху к числу [math]\log_2 (n + 1)[/math], то есть [math]K=\lceil\log_2 (n + 1)\rceil[/math].

В среднем случае сложность можно оценить, используя ту же схему рассмотрения, но находя среднее число итераций по всем элементам массива. Для вида [math]n=2^m-1[/math] : [math]K=\frac{1}{n}\sum_{i=0}^{\log_2 (n+1) -1} i\, 2^i=[\log_2 (n+1)] +\frac{2}{n}-2[/math], в общем виде отличается от формулы не более, чем на 0,5. В лучшем же случае (когда элемент сразу найден) — [math]K=1[/math].

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

1.7 Информационный граф

Граф алгоритма является параметризованным (зависит от размера массива) и недетерминированным (в смысле, что порядок вычислений зависит от начальных данных).

На рисунке ниже изображён граф алгоритма для [math]K = 9[/math]. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op — операция «сравнить значение массива на позиции [math]m_k[/math] с искомым элементом [math]A[/math] и обновить значение пары [math](l_k, r_k)[/math]».

Рисунок 2. Операции в алгоритме бинарного поиска: последовательная версия

1.8 Ресурс параллелизма алгоритма

Сам по себе алгоритм не может быть распараллелен, так как его информационный граф имеет линейный вид. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет порядка [math]K=\log_2 n[/math], содержа [math]K[/math] операций умножения плюс [math]K[/math] операций сложения плюс [math]K[/math] операций сравнения. В таком виде алгоритм должен быть отнесён к алгоритмам логарифмической сложности по высоте параллельной формы. Ширина параллельной формы равна 1, что даёт нам постоянную сложность по ширине параллельной формы.

Однако существует очевидная модификация алгоритма, которая позволяет использовать любое наперёд заданное число процессоров [math]p[/math] — деление не на 2 части, а на [math]p+1[/math] часть. При этом вычисления всех новых узлов, а также сравнение значений в них с [math]A[/math] можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка [math]K=\log_{p+1} n[/math].

1.9 Входные и выходные данные алгоритма

Входные данные: массив [math]x[/math] (элементы [math]x_i[/math]). Число [math]A[/math].

Дополнительные ограничения: массив упорядочен.

Объём входных данных: [math]n[/math].

Выходные данные: индекс элемента [math]A[/math] в массиве, если он есть.

Объём выходных данных: один скаляр.

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности алгоритма: [math]\frac{\log_2 n}{\log_{p+1} n}=\log_2 (p+1)[/math].

Вычислительная мощность алгоритма порядка [math]\frac{\log_2 n}{n}[/math].

Алгоритм абсолютно устойчив, так как действия производятся только над целыми числами, и поэтому погрешность всегда равна 0.

Алгоритм недетерминирован в смысле структуры вычислительного процесса, так как число итераций, а значит и число операций, зависят от входных данных, в частности от искомого значения [math]A[/math]. Однако он детерминирован в смысле, что выдаёт всегда одинаковый результат при одинаковых входных данных.

2 Программная реализация алгоритма

Возможная простейшая реализация алгоритма на языке C:

int binary_find(int n, int *x, long A)
{
int m, left, right;
left = 0; right = n-1;
while (true)
 {
    if (left > right) return (-1); // значение не найдено
    m = left + (right - left) / 2;
    if (x[m] < A) left = m + 1;
    if (x[m] > A) right = m - 1;
    if (x[m] == A) return m;
 }
}

Здесь ряд индексов [math]l_k, m_k, r_k[/math] из математической схемы алгоритма превращён в одну переменную, поскольку требуются только последние значения этих рядов.

2.1 Особенности реализации последовательного алгоритма

Обычно в качестве ответа выводят −1, если число не найдено.

Другие возможные варианты в данной ситуации (выбор зависит от того, как и где будет использоваться метод поиска как базовая единица)[8]:

  1. «магическое число» — то, которое заведомо не получится в качестве результата, если [math]A[/math] найдено. В частности, можно возвращать [math]-(l_k+1)[/math], где [math]k[/math] — последняя итерация перед нарушением условия [math]l_k \lt r_k[/math], передавая таким образом информации о месте, где могло бы находиться [math]A[/math]. Эту информацию можно использовать, в частности, для дальнейшей вставки нового объекта на нужное место в массиве, чтобы оставить его упорядоченным.
  2. специальная константа. Её наличие определяется языком программирования. Например, это может быть null в C# (тогда потребуется использовать тип «int?» в качестве типа результата вместо простого «int»), или … в Python’е
  3. кинуть исключение. Это используется, когда элемент должен был найтись, и дальнейшая работа невозможна, если его не нашлось.

2.1.1 Частые ошибки при реализации

Несмотря на то, что код достаточно прост, в нём есть несколько ловушек, на которые нужно обратить внимание[9]:

  • Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет?[10] Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
    • Использовать код first + (last - first) / 2, который точно не приведёт к переполнениям (то и другое — неотрицательные целые числа).
      • Если first и last — указатели или итераторы, такой код единственно правильный. Преобразование в uintptr_t и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число».
    • Если first и last — типы со знаком, провести расчёт в беззнаковом типе: ((unsigned)first + (unsigned)last) / 2. В Java соответственно: (first + last) >>> 1.
    • Написать расчёт на ассемблере, с использованием флага переноса. Что-то наподобие add eax, b; rcr eax, 1. А вот длинные типы использовать нецелесообразно, first + (last - first) / 2 быстрее.
  • В двоичном поиске часты ошибки на единицу. Поэтому важно протестировать такие случаи: пустой массив (n=0), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли?
  • Иногда требуется, чтобы, если x в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не x, а следующий за ним элемент).[11]

Учёный Йон Бентли утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям[10].

2.2 Локальность данных и вычислений

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

Временная локальность ещё хуже — один и тот же элемент массива никогда не требуется дважды.

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности
Рисунок 3. Реализация двоичного поиска. Общий профиль обращений в память.

На рис. 3 представлен профиль обращений в память для реализации последовательного алгоритма двоичного поиска. В программе задействован массив и три переменные, на рисунке показаны обращения только к элементам этого массива. Каждая точка соответствует одной итерации алгоритма.

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

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

Можно придумать модификацию алгоритма — p-арный поиск, которая позволит использовать любое наперёд заданное число процессоров [math]p[/math] — для этого надо делить область поиска не на 2 части, а на [math]p+1[/math] часть. При этом вычисления всех новых узлов, а также сравнение значений в них с [math]A[/math] можно проводить независимо, а значит параллельно. В этом случае, высота ЯПФ будет порядка [math]K=\log_{p+1} n[/math].

Однако при этом потребуется предусмотреть обмен результатами сравнения своей точки деления на каждом процессоре для определения искомого интервала для следующей итерации. Это потребует минимум одной коллективной операции обмена, что ставит под сомнение эффективность распараллеливания.

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

Использовать алгоритм в любой реализации для архитектур с разделённой памятью смысла не имеет — из-за нелокального доступа к исходным данным и малого количества вычислительных операций даже в параллельной модификации выигрыш будет съедаться коммуникациями.

Применение систем с общей памятью с помощью OpenMP теоретически имеет смысл, однако для получения хоть какого-то ускорения требуется выполнение нескольких условий:

  1. Помещение всего массива исходных данных в общую память.
  2. Статическое создание нитей один раз в начале работы программы.
  3. Выигрыш будет получен только в результате многократного поиска в этом массиве (по общему правилу: число операций внутри параллельной секции должно быть не меньше 1000, чтобы получить ускорение от параллельного вычисления. Это соответствует, например, ~30 поискам в массиве из миллиарда элементов).

2.7 Существующие реализации алгоритма

  1. В стандартной библиотеке языка C есть функция bsearch(), которая обычно реализована с помощью бинарного поиска (однако стандарт не гарантирует этого)[12]
  2. Встроенные в C++ функции: std::lower_bound находит первое вхождение [math]A[/math], std::upper_bound возвращает индекс элемента за всеми [math]A[/math]. Есть также std::binary_search() и std::equal_range().[13]
  3. В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
  4. Microsoft’s .NET Framework 2.0 предлагает статические функции-дженерики двоичного поиска в своей коллекции базовых классов. Например, метод класса System.Array’s BinarySearch<T>(T[] array, T value).[14]
  5. В Python есть модуль bisect[15]

3 См. также

4 Литература

Шаблон:Примечания

  • Ананий В. Левитин. Глава 4. Метод декомпозиции: Бинарный поиск // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: «Вильямс», 2006. — С. 180—183. — ISBN 5-8459-0987-2.
  • Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
  • Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
  • Вирт Н. Алгоритмы + структуры данных = программы. — М.: «Мир», 1985. — С. 28.
  • Волков Е. А. Численные методы. — М.: Физматлит, 2003.
  • Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
  • Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
  • Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. — Энергоатомиздат, 1972.
  • Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  • Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4.

5 Ссылки

  • 1,0 1,1 Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
  • Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10. pp. 180—181. doi:10.1090/psapm/010.
  • Bottenbruch, Hermann (1962). «Structure and Use of ALGOL 60». Journal of the ACM 9 (2): 161—211. Procedure is described at p. 214 (§ 43), titled «Program for Binary Search».
  • Chazelle, Bernard; Liu, Ding (2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. pp. 322—329. doi:10.1145/380752.380818.
  • Chazelle, Bernard; Guibas, Leonidas J. (1986). «Fractional cascading: I. A data structuring technique» (PDF). Algorithmica 1 (1): 133—162. doi:10.1007/BF01840440.
  • Chazelle, Bernard; Guibas, Leonidas J. (1986), «Fractional cascading: II. Applications» (PDF), Algorithmica 1 (1): 163—191, doi:10.1007/BF01840441
  • Асимптотические оценки
  • Я не могу написать бинарный поиск
  • Только 10 % программистов способны написать двоичный поиск
  • 10,0 10,1 Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка
  • В C++ std::lower_bound находит первое вхождение x, а std::upper_bound — элемент, следующий за x.
  • «bsearch — binary search a sorted table». The Open Group Base Specifications (7th ed.). The Open Group. 2013
  • Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2. § 32.6.1 («Binary Search»)
  • «List<T>.BinarySearch Method (T)». Microsoft Developer Network.
  • «8.5. bisect — Array bisection algorithm». The Python Standard Library. Python Software Foundation