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

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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

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

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

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

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

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

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

Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 1946 году.[1] Первое время все реализации работали только для массивов длины [math]\displaystyle{ 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]\displaystyle{ O(n) }[/math]), однако работающий на произвольно упорядоченных массивах. Если сравнивать возможности применения обоих методов, то линейный поиск выгоднее применять 1) для поиска в коротких массивах; 2) когда требуется провести поиск небольшое число раз; 3) в потоковом случае. В отличие от него, бинарный поиск требует предобработку (сортировку, сложность которой не менее [math]\displaystyle{ O(n log_2 n) }[/math]) и особенно полезен, если массив большой и поиск проводится неоднократное (точнее, более, чем порядка [math]\displaystyle{ O(log_2 n) }[/math]) число раз.

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

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

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

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

Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел, упорядоченный по возрастанию (точнее - неубыванию) или убыванию (точнее - невозрастанию), а также число [math]\displaystyle{ A }[/math], которое нужно найти в этом массиве.

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

Формулы метода: элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Анализ на основе теста Apex-Map

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

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

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

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

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

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

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

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

См. также

Литература

  1. ↑ Дональд Кнут . Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0.
  2. ↑ Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10. pp. 180–181. doi:10.1090/psapm/010.
  3. ↑ 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".
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Knuth не указан текст
  5. ↑ 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.
  6. ↑ Chazelle, Bernard; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF). Algorithmica 1 (1): 133–162. doi:10.1007/BF01840440.
  7. ↑ Chazelle, Bernard; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF), Algorithmica 1 (1): 163–191, doi:10.1007/BF01840441
  8. ↑ 8,0 8,1 Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken // Joshua Bloch, Google Research; перевод — Почти во всех реализациях двоичного поиска и сортировки слиянием есть ошибка
  • Ананий В. Левитин. Глава 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.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Двоичный_поиск&oldid=3580