Введение

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

В информатике бинарный поиск, также известный как поиск с половиной интервала, логарифмический поиск или метод деления пополам, — это поисковый алгоритм, который находит позицию целевого значения в отсортированном массиве. Бинарный поиск сравнивает целевое значение со средним элементом массива. Если они не равны, половина массива, в которой целевое значение не может находиться, исключается, и поиск продолжается на оставшейся половине, снова сравнивая целевое значение со средним элементом, до тех пор, пока целевое значение не будет найдено. Если поиск завершается, когда оставшаяся половина пуста, это означает, что целевое значение отсутствует в массиве. Бинарный поиск выполняется за логарифмическое время в худшем случае, выполняя сравнений, где — количество элементов в массиве. Бинарный поиск быстрее линейного поиска, за исключением небольших массивов. Однако для применения бинарного поиска массив должен быть предварительно отсортирован. Существуют специализированные структуры данных, предназначенные для быстрого поиска, такие как хеш-таблицы, которые могут быть просмотрены более эффективно, чем с помощью бинарного поиска. Тем не менее, бинарный поиск можно использовать для решения более широкого круга задач, например, для поиска следующего наименьшего или следующего наибольшего элемента в массиве относительно целевого значения, даже если его там нет. Существует множество вариантов бинарного поиска. В частности, фрактальное каскадирование ускоряет бинарный поиск одного и того же значения в нескольких массивах. Фрактальное каскадирование эффективно решает ряд задач поиска в вычислительной геометрии и во многих других областях. Экспоненциальный поиск расширяет бинарный поиск для неограниченных списков. Структуры данных бинарного дерева поиска и B-дерева основаны на бинарном поиске.

Алгоритм

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

Альтернативная процедура

В описанной выше процедуре алгоритм на каждой итерации проверяет, равен ли средний элемент искомому значению. В некоторых реализациях эта проверка опускается на каждой итерации, и выполняется только когда остается один элемент (при n = 1). Это позволяет ускорить цикл сравнения, так как исключается одно сравнение на итерацию, при этом в среднем требуется лишь одна дополнительная итерация. Первая реализация, в которой была опущена эта проверка, была опубликована Германом Боттенбрухом в 1962 году.

Время выполнения и использование кэша

При анализе производительности бинарного поиска, еще одним важным фактором является время, необходимое для сравнения двух элементов. Для целых чисел и строк время, требуемое для сравнения, увеличивается линейно с ростом длины кодирования (обычно количества бит) элементов. Например, сравнение пары 64-битных беззнаковых целых чисел потребует сравнения до удвоенного количества бит по сравнению с парой 32-битных беззнаковых целых чисел. Наихудший случай наступает, когда целые числа равны. Это может быть существенно, когда длины кодирования элементов велики, например, при использовании больших целочисленных типов или длинных строк, что делает сравнение элементов затратным. Более того, сравнение чисел с плавающей точкой (наиболее распространенного цифрового представления вещественных чисел) часто обходится дороже, чем сравнение целых чисел или коротких строк. На большинстве компьютерных архитектур процессор имеет аппаратный кэш, отдельный от оперативной памяти. Поскольку кэш расположен непосредственно в процессоре, доступ к нему значительно быстрее, но обычно он хранит гораздо меньше данных, чем оперативная память. Поэтому большинство процессоров хранят недавно использованные ячейки памяти, а также ячейки, расположенные рядом с ними. Например, при доступе к элементу массива, в кэш может быть помещен сам элемент и соседние с ним элементы в оперативной памяти, что ускоряет последовательный доступ к элементам массива с близкими индексами (принцип локальности). В отсортированном массиве бинарный поиск может переходить к удаленным участкам памяти, если массив большой, в отличие от алгоритмов (таких как линейный поиск и линейное зондирование в хеш-таблицах), которые обращаются к элементам последовательно. Это незначительно увеличивает время выполнения бинарного поиска для больших массивов на большинстве систем.

Бинарный поиск против других схем

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

Линейный поиск

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

Деревья

Двоичное дерево поиска — это структура данных двоичного дерева, работающая на основе принципа двоичного поиска. Записи дерева упорядочены, и каждая запись в дереве может быть найдена с помощью алгоритма, аналогичного двоичному поиску, в среднем за логарифмическое время. Вставка и удаление также в среднем требуют логарифмического времени в двоичных деревьях поиска. Это может быть быстрее, чем линейное время вставки и удаления в сортированных массивах, при этом двоичные деревья сохраняют возможность выполнять все операции, возможные с сортированным массивом, включая запросы по диапазону и приблизительные запросы. Однако хеширование бесполезно для приблизительных совпадений, таких как поиск следующего меньшего, следующего большего и ближайшего ключа, поскольку единственная информация при неудачном поиске заключается в том, что искомый элемент отсутствует в какой-либо записи. Двоичный поиск идеально подходит для таких совпадений, выполняя их за логарифмическое время. Двоичный поиск также поддерживает приблизительные совпадения. Некоторые операции, такие как поиск наименьшего и наибольшего элемента, могут быть эффективно выполнены на сортированных массивах, но не на хеш-таблицах. Для приблизительных результатов фильтры Блума, другая вероятностная структура данных на основе хеширования, хранят набор ключей, кодируя их с помощью битового массива и нескольких хеш-функций. В большинстве случаев фильтры Блума гораздо более экономичны по памяти, чем битовые массивы, и не намного медленнее: при использовании *k* хеш-функций запросы на принадлежность требуют всего *O(k)* времени. Однако фильтры Блума подвержены ложным срабатываниям. Существуют улучшения фильтра Блума, которые повышают его эффективность или поддерживают удаление; например, фильтр кукушки использует кукушечное хеширование для получения этих преимуществ.

Другие структуры данных

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

Фракционная каскадная система

Фракционное каскадирование — это техника, ускоряющая бинарный поиск одного и того же элемента в нескольких отсортированных массивах. Поиск по каждому массиву отдельно требует времени O(n), где n — количество массивов. Фракционное каскадирование позволяет сократить это время до O(log n), сохраняя в каждом массиве специфическую информацию о каждом элементе и его позиции в остальных массивах. Фракционное каскадирование изначально было разработано для эффективного решения различных задач вычислительной геометрии. Впоследствии оно нашло применение и в других областях, таких как интеллектуальный анализ данных и маршрутизация интернет-протоколов.

Шумный поиск в двоичном пакете

Шумные алгоритмы бинарного поиска решают задачу, возникающую, когда алгоритм не может надежно сравнивать элементы массива. Для каждой пары элементов существует определенная вероятность того, что алгоритм совершит ошибочное сравнение. Шумный бинарный поиск позволяет найти правильную позицию целевого элемента с заданной вероятностью, определяющей надежность полученной позиции. Любой алгоритм шумного бинарного поиска должен выполнять не менее сравнений в среднем, где – функция двоичной энтропии, а – вероятность выдачи неверной позиции. Задача шумного бинарного поиска может рассматриваться как частный случай игры Рени-Улама, варианта игры "Двадцать вопросов", в которой ответы могут быть неверными.

Квантовый бинарный поиск

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

История

Идея сортировки списка элементов для ускорения поиска восходит к античности. Самым ранним известным примером является вавилонская табличка Инакибит-Ану, датируемая примерно 200 годом до нашей эры. На табличке содержалось около 500 шестидесятеричных чисел и их обратных величин, отсортированных в лексикографическом порядке, что облегчало поиск конкретной записи. Кроме того, на Эгейских островах были обнаружены несколько списков имен, отсортированных по первой букве. «Католикон», латинский словарь, завершенный в 1286 году нашей эры, стал первым трудом, в котором описаны правила сортировки слов в алфавитном порядке, а не только первых нескольких букв. В 1946 году Джон Мокли впервые упомянул бинарный поиск в рамках лекций в Школе Мура – основополагающего и фундаментального университетского курса по вычислительной технике. В 1957 году Уильям Уэсли Петерсон опубликовал первый метод интерполяционного поиска. Все опубликованные алгоритмы бинарного поиска работали только для массивов, длина которых была на единицу меньше степени двойки, до 1960 года, когда Деррик Генри Лемер опубликовал алгоритм бинарного поиска, работающий со всеми массивами. В 1962 году Герман Боттенбрюх представил реализацию бинарного поиска на языке ALGOL 60, в которой проверка на равенство была помещена в конец, что увеличивало среднее количество итераций на единицу, но уменьшало количество сравнений за итерацию до одного.

Вопросы внедрения

Когда Джон Бентли задал бинарный поиск в качестве задачи для курса профессиональных программистов, он обнаружил, что девяносто процентов не смогли предоставить корректное решение после нескольких часов работы, главным образом из-за того, что неправильные реализации либо не запускались, либо возвращали неверный ответ в редких граничных случаях. Исследование, опубликованное в 1988 году, показало, что точный код для него встречается лишь в пяти из двадцати учебников. Более того, собственная реализация Бентли двоичного поиска, опубликованная в его книге «Programming Pearls» 1986 года, содержала ошибку переполнения, которая оставалась незамеченной более двадцати лет. В библиотеке языка программирования Java реализация двоичного поиска содержала ту же ошибку переполнения более девяти лет. В практической реализации переменные, используемые для представления индексов, часто имеют фиксированный размер (целые числа), что может привести к арифметическому переполнению для очень больших массивов. Если средняя точка интервала вычисляется как , то значение может превысить диапазон целых чисел типа данных, используемого для хранения средней точки, даже если и находятся в пределах диапазона. Если и неотрицательны, этого можно избежать, вычисляя среднюю точку как . Бесконечный цикл может возникнуть, если условия выхода из цикла определены некорректно. Если превышает , поиск не удался и должен сообщить об этом. Кроме того, цикл должен завершаться, когда целевой элемент найден, или, в случае реализации, где эта проверка перенесена в конец, в конце должны быть проверки на успешность или неудачу поиска. Бентли обнаружил, что большинство программистов, неправильно реализовавших двоичный поиск, допустили ошибку при определении условий выхода. Стандартная библиотека C++ предоставляет функции binary search, lower bound, upper bound и equal range. Стандартная библиотека D Phobos, в модуле std.range, предоставляет тип SortedRange (возвращаемый функциями sort и assumeSorted) с методами contains, equalRange, lowerBound и trisect, которые по умолчанию используют методы бинарного поиска для диапазонов, предлагающих произвольный доступ. COBOL предоставляет оператор SEARCH ALL для выполнения бинарных поисков в упорядоченных таблицах COBOL. Стандартный пакет библиотеки сортировки Go содержит функции Search, SearchInts, SearchFloat64s и SearchStrings, которые реализуют общий бинарный поиск, а также специализированные реализации для поиска в срезах целых чисел, чисел с плавающей точкой и строк соответственно. Java предлагает набор перегруженных статических методов binarySearch в классах и в стандартном пакете java.util для выполнения бинарных поисков в массивах Java и списках соответственно. Microsoft .NET Framework 2.0 предлагает статические обобщенные версии алгоритма бинарного поиска в своих базовых классах коллекций. Примером может служить метод System.Array.BinarySearch<T>(T[] array, T value). Для Objective-C фреймворк Cocoa предоставляет метод NSArray indexOfObject:inSortedRange:options:usingComparator: в Mac OS X 10.6+. Фреймворк Apple Core Foundation C также содержит функцию CFArrayBSearchValues. Python предоставляет модуль bisect, который поддерживает список в отсортированном порядке без необходимости его сортировки после каждой вставки. Класс Ruby's Array включает в себя метод bsearch со встроенным приближенным сопоставлением.