Двоичный поиск: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Нет описания правки |
Нет описания правки |
||
| Строка 1: | Строка 1: | ||
{{algorithm | {{algorithm | ||
| name = Бинарный поиск | | name = Бинарный поиск | ||
| serial_complexity = <math>\log_2 n</math> | | serial_complexity = <math>\log_2 n</math> (в худшем и среднем случаях) | ||
| pf_height = ? | | pf_height = ? | ||
| pf_width = ? | | pf_width = ? | ||
| Строка 9: | Строка 9: | ||
Основные авторы описания: [[User:AntonChupin|А. В. Чупин]]. | Основные авторы описания: [[User:AntonChupin|А. В. Чупин]]. | ||
Синонимы названия метода: '''двоичный поиск''', '''бинарный поиск''', '''метод деления пополам''', '''дихотомия'''. | Синонимы названия метода: '''двоичный поиск''', '''бинарный поиск''', '''метод деления пополам''', '''метод половинного деления''', '''дихотомия'''. | ||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Метод двоичного поиска''' используется в качестве быстрого варианта поиска в заранее отсортированном массиве. Получил распространение благодаря как наименьшей из возможных высоте | '''Метод двоичного поиска''' используется в качестве быстрого варианта поиска в заранее отсортированном массиве. Получил распространение благодаря как наименьшей из возможных высоте алгоритма, так и из-за ряда своих вычислительных характеристик, а также (в среде нечисленных алгоритмов) из-за своей рекурсивности, то есть лёгкости записи. | ||
Основная идея заключается в дроблении массива на половины и дальнейшем рекурсивном поиске в одной из них. | |||
Первое упоминание метода было сделано на лекциях школы Мура Джоном Мокли в 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>) число раз. | |||
Непрерывным аналогом является [https://ru.wikipedia.org/wiki/Метод_бисекции метод бисекции] (метод деления пополам) нахождения корня непрерывной функции на заданном отрезке. | |||
Метод позволяет различные обобщения и видоизменения: | |||
* [[Однородный двоичный поиск]], был представлен А. К. Чандрой в 1971 году Дональду Кнуту, который опубликовал его в своей монографии<ref name="Knuth"/>. | |||
* [[Троичный поиск]], когда отрезок делится на три части. Применяется для поиска положения экстремума функции. | |||
* [[Интерполирующий поиск]], делящий область поиска не пополам, а предсказывающий позицию искомого элемента на основе разницы значений. Работает быстрее, если элементы распределены достаточно равномерно - d среднем <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>. | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| Строка 51: | Строка 66: | ||
Обычно в качестве ответа выводят -1, если число не найдено. | Обычно в качестве ответа выводят -1, если число не найдено. | ||
==== Частые ошибки при реализации ==== | |||
Несмотря на то, что код достаточно прост, в нём есть несколько ловушек, на которые нужно обратить внимание: | |||
* Что будет, если <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</code> и <code>last</code> — указатели или [[итератор]]ы, такой код единственно правильный. Преобразование в <code>uintptr_t</code> и дальнейший расчёт в этом типе нарушает абстракцию, и нет гарантии, что результат останется корректным указателем. Разумеется, чтобы сохранялась сложность алгоритма, нужны быстрые операции «итератор+число → итератор», «итератор−итератор → число». | |||
** Если <code>first</code> и <code>last</code> — типы со знаком, провести расчёт в беззнаковом типе: <code>((unsigned)first + (unsigned)last) / 2</code>. В [[Java]] соответственно: <code>(first + last) >>> 1</code>. | |||
** Написать расчёт на ассемблере, с использованием [[флаг переноса|флага переноса]]. Что-то наподобие <code>add eax, b; rcr eax, 1</code>. А вот [[длинная арифметика|длинные типы]] использовать нецелесообразно, <code>first + (last - first) / 2</code> быстрее. | |||
* В двоичном поиске часты [[ошибка на единицу|ошибки на единицу]]. Поэтому важно протестировать такие случаи: пустой массив (<code>n=0</code>), ищем отсутствующее значение (слишком большое, слишком маленькое и где-то в середине), ищем первый и последний элемент. Не выходит ли алгоритм за границы массива? Не зацикливается ли? | |||
* Иногда требуется, чтобы, если <code>x</code> в цепочке существует в нескольких экземплярах, находило не любой, а обязательно первый (как вариант: последний; либо вообще не <code>x</code>, а следующий за ним элемент).{{-1|<ref>В [[C++]] <code>std::lower_bound</code> находит первое вхождение <code>x</code>, а <code>std::upper_bound</code> — элемент, следующий за <code>x</code>.</ref>}} Код на Си в такой ситуации находит первый из равных, более простой код на Си++ — какой попало. | |||
Учёный [[Бентли, Йон|Йон Бентли]] утверждает, что 90 % студентов, разрабатывая двоичный поиск, забывают учесть какое-либо из этих требований. И даже в код, написанный самим Йоном и ходивший из книги в книгу, вкралась ошибка: код не стоек к переполнениям<ref name="joshua"/>. | |||
=== Локальность данных и вычислений === | === Локальность данных и вычислений === | ||
==== Локальность реализации алгоритма ==== | ==== Локальность реализации алгоритма ==== | ||
| Строка 63: | Строка 89: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
# Встроенные в C++ функции: <code>std::lower_bound</code> находит первое вхождение <math>A</math>, <code>std::upper_bound</code> возвращает индекс элемента за всеми <math>A</math>. | |||
# В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator. | |||
== См. также == | |||
* [[Метод половинного деления]] | |||
* [[Троичный поиск]] | |||
* [[Интерполирующий поиск]] | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
* Ананий В. Левитин. Глава 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. | |||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
Версия от 22:00, 29 июня 2016
| Бинарный поиск | |
| Последовательный алгоритм | |
| Последовательная сложность | [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
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Встроенные в C++ функции:
std::lower_boundнаходит первое вхождение [math]\displaystyle{ A }[/math],std::upper_boundвозвращает индекс элемента за всеми [math]\displaystyle{ A }[/math]. - В стандартной библиотеке Java реализация двоичного поиска выглядит так: java.util.Arrays.binarySearch(T[] array, T value[, Comparator c]). При этом он может быть расширен через интерфейс Comparator.
См. также
Литература
- ↑ Дональд Кнут . Искусство программирования, том 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.