Двоичный поиск
| Бинарный поиск | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\log_2 n[/math] (в худшем и среднем случаях) |
| Объём входных данных | упорядоченный массив длины [math]n[/math], число [math]A[/math] |
| Объём выходных данных | индекc элемента |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | ? |
| Ширина ярусно-параллельной формы | ? |
Основные авторы описания: А. В. Чупин.
Синонимы названия метода: двоичный поиск, бинарный поиск, метод деления пополам, метод половинного деления, дихотомия.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 См. также
- 4 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод двоичного поиска используется в качестве быстрого варианта поиска в заранее отсортированном массиве. Получил распространение благодаря как наименьшей из возможных высоте алгоритма, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи.
Основная идея заключается в дроблении массива на половины и дальнейшем рекурсивном поиске в одной из них.
Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 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 году Дональду Кнуту, который опубликовал его в своей монографии[4].
- Троичный поиск, когда отрезок делится на три части. Применяется для поиска положения экстремума функции.
- Интерполирующий поиск, делящий область поиска не пополам, а предсказывающий позицию искомого элемента на основе разницы значений. Работает быстрее, если элементы распределены достаточно равномерно - d среднем [math]O(log log n)[/math]. В худшем случае, работает за [math]O(n)[/math]).
- Дробный спуск (англ. fractional cascading), предложенный в 1986 году Бернаром Шазеллем и Леонидасом Дж. Гуйбасом, как техника ускорения бинарного поиска в многомерных массивах.[5][6][7].
1.2 Математическое описание алгоритма
Исходные данные: одномерный массив [math]n[/math] чисел, упорядоченный по возрастанию (точнее - неубыванию) или убыванию (точнее - невозрастанию), а также число [math]A[/math], которое нужно найти в этом массиве.
Вычисляемые данные: индекс элемента, равного искомому (или ответ, что такого элемента нет).
Формулы метода: элементы на каждом этапе алгоритма рассматриваются в виде непрерывного отрезка массива. В каждой из пар находится сумма составляющих её элементов. На следующем этапе на пары разбиваются уже эти суммы (и те элементы, которые не вошли в уже вычисленные суммы), и т. д.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро последовательно-параллельного метода суммирования можно составить как из операций сравнения и получения середины отрезка, так и (рекуррентно) из набора реализаций метода бинарного поиска в массиве меньшего размера.
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
Входные данные: массив [math]x[/math] (элементы [math]x_i[/math]). Число [math]A[/math].
Дополнительные ограничения: массив упорядочен.
Объём входных данных: [math]n[/math].
Выходные данные: индекс элемента [math]A[/math] в массиве, если он есть.
Объём выходных данных: один скаляр.
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
Обычно в качестве ответа выводят -1, если число не найдено.
2.1.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].
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.2.1.3 Анализ на основе теста Apex-Map
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
2.5 Динамические характеристики и эффективность реализации алгоритма
2.6 Выводы для классов архитектур
2.7 Существующие реализации алгоритма
- Встроенные в C++ функции:
std::lower_boundнаходит первое вхождение [math]A[/math],std::upper_boundвозвращает индекс элемента за всеми [math]A[/math]. - В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
3 См. также
4 Литература
- ↑ Дональд Кнут . Искусство программирования, том 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".
- ↑ Ошибка цитирования Неверный тег
<ref>; для сносокKnuthне указан текст - ↑ 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
- ↑ 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.
