Двоичный поиск: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
| Строка 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. | ||
[[Категория:Начатые статьи]] | [[Категория:Начатые статьи]] | ||
Версия 01:00, 30 июня 2016
| Бинарный поиск | |
| Последовательный алгоритм | |
| Последовательная сложность | [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.
