Алгоритм двоичного поиска - Binary search algorithm

Алгоритм двоичного поиска
Двоичный поиск Depiction.svg
Визуализация алгоритма двоичного поиска, где 7 - целевое значение
Класс Алгоритм поиска
Структура данных Множество
Наихудшая производительность O (журнал n )
Лучшая производительность О (1)
Средняя производительность O (журнал n )
Сложность пространства в наихудшем случае О (1)

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

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

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

Алгоритм

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

Процедура

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

  1. Установите на и на .
  2. Если поиск прекращается как безуспешный.
  3. Набор (положение среднего элемента) на пол из , который является наибольшим целое , меньшей или равным .
  4. Если установите на и перейти к шагу 2.
  5. Если установите на и перейти к шагу 2.
  6. Теперь поиск завершен; вернуться .

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

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

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

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

В описанной выше процедуре алгоритм проверяет, равен ли средний элемент ( ) target ( ) на каждой итерации. Некоторые реализации пропускают эту проверку на каждой итерации. Алгоритм будет выполнять эту проверку только тогда, когда останется один элемент (когда ). Это приводит к более быстрому циклу сравнения, поскольку исключается одно сравнение на итерацию. Однако в среднем требуется еще одна итерация.

Герман Боттенбрух опубликовал первую реализацию, которая исключила эту проверку в 1962 году.

  1. Установите на и на .
  2. Хотя ,
    1. Набор (положение среднего элемента) к потолку из , который является наименьшее целое число , большее или равное .
    2. Если установите в .
    3. Иначе ; установлен на .
  3. Теперь поиск завершен. Если , вернись . В противном случае поиск прекращается как безуспешный.

Где ceilфункция потолка, псевдокод для этой версии:

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

Повторяющиеся элементы

Процедура может вернуть любой индекс, элемент которого равен целевому значению, даже если в массиве есть повторяющиеся элементы. Например, если искомый массив был и был целью , то алгоритм будет правильно возвращать либо 4-й (индекс 3), либо 5-й (индекс 4) элемент. В этом случае обычная процедура вернет 4-й элемент (индекс 3). Он не всегда возвращает первый дубликат (подумайте, какой по-прежнему возвращает 4-й элемент). Однако иногда необходимо найти крайний левый элемент или крайний правый элемент для целевого значения, которое дублируется в массиве. В приведенном выше примере 4-й элемент является крайним левым элементом значения 4, а 5-й элемент является крайним правым элементом значения 4. Альтернативная процедура, описанная выше, всегда будет возвращать индекс самого правого элемента, если такой элемент существует.

Процедура поиска крайнего левого элемента

Чтобы найти крайний левый элемент, можно использовать следующую процедуру:

  1. Установите на и на .
  2. Хотя ,
    1. Набор (положение среднего элемента) на пол из , который является наибольшим целое , меньшей или равным .
    2. Если установите в .
    3. Иначе ; установлен на .
  3. Вернуться .

Если и , то это крайний левый элемент, равный . Даже если не в массиве, является ранг из массива, или количество элементов в массиве, которые меньше .

floorПсевдокод для этой версии, где находится функция пола:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Порядок поиска крайнего правого элемента

Чтобы найти самый правый элемент, можно использовать следующую процедуру:

  1. Установите на и на .
  2. Хотя ,
    1. Набор (положение среднего элемента) на пол из , который является наибольшим целое , меньшей или равным .
    2. Если установите в .
    3. Иначе ; установлен на .
  3. Вернуться .

Если и , то это самый правый элемент, который равен . Даже если нет в массиве, количество элементов в массиве больше, чем .

floorПсевдокод для этой версии, где находится функция пола:

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Примерные совпадения

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

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

  • Ранговые запросы могут выполняться с помощью процедуры поиска крайнего левого элемента . Число элементов меньше целевого значения возвращается процедурой.
  • Запросы-предшественники могут выполняться с запросами ранжирования. Если ранг целевого значения равен , то его предшественник  .
  • Для запросов-преемников может использоваться процедура поиска самого правого элемента . Если результат выполнения процедуры для целевого значения равен , то преемником целевого значения является  .
  • Ближайшим соседом целевого значения является его предшественник или последователь, в зависимости от того, что ближе.
  • Запросы диапазона также просты. Как только ранги двух значений известны, количество элементов больше или равных первому значению и меньше второго является разницей между двумя рангами. Этот счетчик может быть увеличен или уменьшен на единицу в зависимости от того, следует ли считать конечные точки диапазона частью диапазона и содержит ли массив записи, соответствующие этим конечным точкам.

Представление

Дерево , представляющее двоичный поиск. Здесь ищется массив , а целевое значение - .
Худший случай достигается, когда поиск достигает самого глубокого уровня дерева, в то время как лучший случай достигается, когда целевым значением является средний элемент.

С точки зрения количества сравнений производительность двоичного поиска можно проанализировать, просмотрев выполнение процедуры в двоичном дереве. Корневой узел дерева - средний элемент массива. Средний элемент нижней половины - это левый дочерний узел корня, а средний элемент верхней половины - это правый дочерний узел корня. Остальная часть дерева построена аналогичным образом. Начиная с корневого узла, выполняется обход левого или правого поддеревья в зависимости от того, больше или меньше целевое значение, чем рассматриваемый узел.

В худшем случае двоичный поиск выполняет итерации цикла сравнения, где обозначение обозначает минимальную функцию, которая дает наибольшее целое число, меньшее или равное аргументу, и является двоичным логарифмом . Это связано с тем, что наихудший случай достигается, когда поиск достигает самого глубокого уровня дерева, и в дереве всегда есть уровни для любого двоичного поиска.

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

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

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

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

Космическая сложность

Двоичный поиск требует трех указателей на элементы, которые могут быть индексами массива или указателями на ячейки памяти, независимо от размера массива. Следовательно, пространственная сложность двоичного поиска заключается в модели вычисления слова RAM .

Вывод среднего случая

Среднее количество итераций, выполняемых двоичным поиском, зависит от вероятности поиска каждого элемента. Средний случай отличается для успешных поисков и неудачных поисков. Предполагается, что каждый элемент с одинаковой вероятностью будет подвергнут успешному поиску. Для безуспешных поисков предполагается, что интервалы между и внешними элементами будут искать с одинаковой вероятностью. Средний случай успешного поиска - это количество итераций, необходимых для поиска каждого элемента ровно один раз, деленное на количество элементов. Средний случай неудачных поисков - это количество итераций, необходимых для поиска элемента в каждом интервале ровно один раз, деленное на интервалы.

Успешные поиски

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

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

Например, в массиве из 7 элементов корень требует одной итерации, два элемента ниже корня требуют двух итераций, а четыре элемента ниже требуют трех итераций. В этом случае длина внутреннего пути составляет:

Среднее количество итераций будет основано на уравнении для среднего случая. Сумму можно упростить до:

Подставляя уравнение для в уравнение для :

Для целого числа это эквивалентно уравнению для среднего случая успешного поиска, указанного выше.

Неудачные поиски

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

Подобным образом эту проблему можно свести к определению минимальной длины внешнего пути всех двоичных деревьев с узлами. Для всех двоичных деревьев длина внешнего пути равна длине внутреннего пути плюс . Подставляя уравнение для :

Подставляя уравнение для в уравнение для , можно определить средний случай неудачных поисков:

Выполнение альтернативной процедуры

Каждая итерация процедуры двоичного поиска, определенной выше, выполняет одно или два сравнения, проверяя, равен ли средний элемент целевому на каждой итерации. Предполагая, что вероятность поиска каждого элемента одинакова, каждая итерация выполняет в среднем 1,5 сравнения. Вариант алгоритма проверяет, равен ли средний элемент целевому в конце поиска. В среднем это исключает половину сравнения из каждой итерации. Это немного сокращает время, затрачиваемое на одну итерацию на большинстве компьютеров. Однако это гарантирует, что поиск занимает максимальное количество итераций, в среднем добавляя одну итерацию к поиску. Поскольку в худшем случае цикл сравнения выполняется только один раз, небольшое увеличение эффективности на одну итерацию не компенсирует лишнюю итерацию для всех, кроме очень больших .

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

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

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

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

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

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

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

Деревья

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

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

Однако двоичный поиск обычно более эффективен для поиска, поскольку деревья двоичного поиска, скорее всего, будут несовершенно сбалансированы, что приведет к несколько худшей производительности, чем двоичный поиск. Это даже применимо к сбалансированным двоичным деревьям поиска , двоичным деревьям поиска, которые балансируют свои собственные узлы, потому что они редко создают дерево с наименьшим возможным уровнем. За исключением сбалансированных двоичных деревьев поиска, дерево может быть сильно разбалансировано с несколькими внутренними узлами с двумя дочерними элементами, в результате чего среднее и худшее время поиска приближается к сравнениям. Деревья двоичного поиска занимают больше места, чем отсортированные массивы.

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

Хеширование

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

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

Связанная с поиском проблема - это установка членства . Любой алгоритм, который выполняет поиск, например двоичный поиск, также может использоваться для определения членства. Существуют и другие алгоритмы, более подходящие для членства в множестве. Битовый массив является самым простым, полезным , когда диапазон ключей ограничивается. Он компактно хранит набор битов , каждый из которых представляет отдельный ключ в диапазоне ключей. Битовые массивы работают очень быстро и требуют только времени. Тип Judy1 массива Judy эффективно обрабатывает 64-битные ключи.

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

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

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

Вариации

Единый двоичный поиск

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

В единообразном двоичном поиске вместо нижней и верхней границ сохраняется разница в индексе среднего элемента от текущей итерации до следующей итерации. Поисковая таблица , содержащая различия заранее вычислена. Например, если поиск выполняется в массиве [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , средний элемент ( ) будет равен 6 . В этом случае средний элемент левого подмассива ( [1, 2, 3, 4, 5] ) равен 3, а средний элемент правого подмассива ( [7, 8, 9, 10, 11] ) - 9 . Единый двоичный поиск сохранит значение 3, поскольку оба индекса отличаются от 6 на ту же величину. Чтобы уменьшить пространство поиска, алгоритм либо добавляет, либо вычитает это изменение из индекса среднего элемента. Равномерный двоичный поиск может быть быстрее в системах, где неэффективно вычислять среднюю точку, например, на компьютерах с десятичными числами .

Экспоненциальный поиск

Визуализация экспоненциального поиска с нахождением верхней границы для последующего бинарного поиска

Экспоненциальный поиск расширяет двоичный поиск до неограниченных списков. Он начинается с поиска первого элемента с индексом, который является степенью двойки и больше целевого значения. После этого он устанавливает этот индекс как верхнюю границу и переключается на двоичный поиск. Поиск требует итераций перед запуском двоичного поиска и не более чем итераций двоичного поиска, где - позиция целевого значения. Экспоненциальный поиск работает с ограниченными списками, но становится улучшением по сравнению с двоичным поиском только в том случае, если целевое значение находится рядом с началом массива.

Интерполяционный поиск

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

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

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

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

Дробное каскадирование

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

Дробное каскадирование - это метод, который ускоряет двоичный поиск одного и того же элемента в нескольких отсортированных массивах. Для поиска каждого массива отдельно требуется время, где - количество массивов. Дробное каскадирование сводит это к тому , что в каждом массиве хранится конкретная информация о каждом элементе и его положении в других массивах.

Изначально дробное каскадирование было разработано для эффективного решения различных задач вычислительной геометрии . Дробное каскадирование применялось повсеместно, например, при интеллектуальном анализе данных и маршрутизации по Интернет-протоколу .

Обобщение на графы

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

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

При зашумленном двоичном поиске есть определенная вероятность, что сравнение некорректно.

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

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

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

История

Идея сортировки списка элементов для более быстрого поиска восходит к древности. Самым ранним известным примером была табличка Инакибит-Ану из Вавилона, датируемая ок.  200 г. до н . Э. Табличка содержала около 500 шестидесятеричных чисел и их обратные, отсортированные в лексикографическом порядке , что облегчало поиск конкретной записи. Кроме того, на Эгейских островах было обнаружено несколько списков имен, отсортированных по первой букве . Католикон , латинский словарь, законченный в 1286 году н.э., был первой работой, описывающей правила сортировки слов в алфавитном порядке, а не только по первым буквам.

В 1946 году Джон Мочли впервые упомянул о двоичном поиске в рамках лекций школы Мура , основополагающего и основополагающего курса колледжа по информатике. В 1957 году Уильям Уэсли Петерсон опубликовал первый метод интерполяционного поиска. Каждый опубликованный алгоритм двоичного поиска работал только с массивами, длина которых на единицу меньше степени двойки, до 1960 года, когда Деррик Генри Лемер опубликовал алгоритм двоичного поиска, который работал со всеми массивами. В 1962 году Герман Боттенбрух представил реализацию двоичного поиска на Алголе 60 , в которой сравнение на равенство помещается в конец , увеличивая среднее количество итераций на одну, но уменьшая до одного количество сравнений на итерацию. Равномерная бинарный поиск был разработан К. Чандра из Стэнфордского университета в 1971 г. В 1986 году Бернард Чазел и Леонидас J Гибас ввел дробное каскадирование в качестве метода для решения многочисленных задач поиска в вычислительной геометрии .

Проблемы реализации

Хотя основная идея двоичного поиска относительно проста, детали могут быть на удивление сложными.

Когда Джон Бентли обозначил двоичный поиск как проблему в курсе для профессиональных программистов, он обнаружил, что девяносто процентов не смогли предоставить правильное решение после нескольких часов работы над ним, в основном из-за того, что некорректные реализации не выполнялись или возвращали неправильный ответ в редких случаях. крайние случаи . Исследование, опубликованное в 1988 году, показывает, что точный код для него можно найти только в пяти из двадцати учебников. Более того, собственная реализация двоичного поиска Бентли, опубликованная в его книге « Жемчужины программирования» 1986 года , содержала ошибку переполнения, которая оставалась незамеченной более двадцати лет. Язык программирования Java реализация библиотеки бинарного поиска была такая же ошибка переполнения в течение более девяти лет.

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

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

Поддержка библиотеки

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

  • C предоставляет эту функцию bsearch() в своей стандартной библиотеке , которая обычно реализуется посредством двоичного поиска, хотя официальный стандарт этого не требует.
  • C ++ «s Standard Template Library предоставляет функции binary_search(), lower_bound(), upper_bound()и equal_range().
  • D стандартная библиотека «s Фобос, в std.rangeмодуле обеспечивает тип SortedRange(возвращенный sort()и assumeSorted()функциями) с методами contains(), equaleRange(), lowerBound()и trisect(), которые используют бинарные методы поиска по умолчанию для диапазонов , которые предлагают произвольный доступ.
  • COBOL предоставляет команду SEARCH ALLдля выполнения двоичного поиска в упорядоченных таблицах COBOL.
  • Go «s sortстандартный пакет библиотеки содержит функции Search, SearchInts, SearchFloat64sи SearchStrings, которые реализуют общий бинарный поиск, а также конкретные реализации для поиска ломтиков целых чисел, чисел с плавающей точкой и строк, соответственно.
  • Java предлагает набор перегруженных binarySearch() статических методов в классах Arraysи Collectionsв стандартном java.utilпакете для выполнения двоичного поиска в массивах Java и в Lists соответственно.
  • Microsoft «s .NET Framework 2.0 предлагает статические общие версии двоичного алгоритма поиска в его коллекции базовых классов. Примером может служить System.Arrayметод России BinarySearch<T>(T[] array, T value).
  • Для Objective-C структура Какао предоставляет NSArray -indexOfObject:inSortedRange:options:usingComparator:метод в Mac OS X 10.6+. Фреймворк Apple Core Foundation C также содержит CFArrayBSearchValues()функцию.
  • Python предоставляет bisectмодуль.
  • Класс Ruby Array включает bsearchметод со встроенным приблизительным сопоставлением.

Смотрите также

Примечания и ссылки

Эта статья была отправлена ​​в WikiJournal of Science для внешнего научного рецензирования в 2018 году ( отчеты рецензентов ). Обновленный контент был повторно интегрирован на страницу Википедии по лицензии CC-BY-SA-3.0 ( 2019 ). Проверенная версия записи: Энтони Лин; и другие. (2 июля 2019 г.). «Алгоритм двоичного поиска» (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347 / WJS / 2019.005 . ISSN  2470-6345 . Викиданные  Q81434400 .

Примечания

Цитаты

Источники

внешние ссылки