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

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

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

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

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

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

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

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

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

Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году. Первое время все реализации работали только для массивов длины [math]2^k-1[/math], пока в 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.[18][40][41]

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

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

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

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

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

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

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] в худшем случае (когда элемент не найден, или находится на последнем шагу) легко оценить, если количество элементов в массиве [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;
 }
}

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

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

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

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 Частые ошибки при реализации

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

• Что будет, если first и last по отдельности умещаются в свой тип, а first+last — нет? Если теоретически возможны массивы столь большого размера, приходится идти на ухищрения:
  • Использовать код 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, а следующий за ним элемент).

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

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

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

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

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

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

2.2.1.1 Структура обращений в память и качественная оценка локальности

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

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

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

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

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

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

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

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

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

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

1. Встроенные в C++ функции: std::lower_bound находит первое вхождение [math]A[/math], std::upper_bound возвращает индекс элемента за всеми [math]A[/math].
2. В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.

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 Внешние ссылки

• Метод двоичного поиска в Википедии
• Алгоритм в библиотеке алгоритмов Algolist.
• Реализации алгоритма в Викиучебнике