Бинарный поиск

Эта статья о поиске в конечном отсортированном массиве. Для поиска значений непрерывной функции см. метод деления пополам .

Бинарный поиск

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

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

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

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

Алгоритм

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

Процедура

Учитывая массив $A$ из $n$ элементы со значениями или записями $A_{0},A_{1},A_{2},\ldots ,A_{n-1}$отсортировано так, что $A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}$и целевое значение $T$, следующая подпрограмма использует двоичный поиск для поиска индекса $T$ в $A$.

1. Набор $L$ к $0$ и $R$ к $n-1$.
2. Если $L>R$, поиск завершается как безуспешный.
3. Набор $m$ (положение среднего элемента) пола до ${\frac {L+R}{2}}$, которое является наибольшим целым числом, меньшим или равным ${\frac {L+R}{2}}$.
4. Если $A_{m}<T$, набор $L$ к $m+1$ и перейдите к шагу 2.
5. Если $A_{m}>T$, набор $R$ к $m-1$ и перейдите к шагу 2.
6. Сейчас $A_{m}=T$, поиск завершен; возвращаться $m$.

Эта итеративная процедура отслеживает границы поиска с помощью двух переменных $L$ и $R$. Процедура может быть выражена в псевдокоде следующим образом, где имена и типы переменных остаются такими же, как указано выше: floor — функция пола , и unsuccessful относится к конкретному значению, которое сообщает о неудаче поиска.

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

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

Альтернативно, алгоритм может потолок принять ${\frac {L+R}{2}}$. Это может изменить результат, если целевое значение появляется в массиве более одного раза.

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

В приведенной выше процедуре алгоритм проверяет, является ли средний элемент ( $m$) равно целевому ( $T$) в каждой итерации. Некоторые реализации исключают эту проверку во время каждой итерации. Алгоритм будет выполнять эту проверку только тогда, когда останется один элемент (когда $L=R$). Это приводит к более быстрому циклу сравнения, поскольку на каждой итерации исключается одно сравнение, хотя в среднем требуется только одна дополнительная итерация.

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

1. Набор $L$ к $0$ и $R$ к $n-1$.
2. Пока $L\neq R$,
   1. Набор $m$ (положение среднего элемента) потолка до ${\frac {L+R}{2}}$, что является наименьшим целым числом, большим или равным ${\frac {L+R}{2}}$.
   2. Если $A_{m}>T$, набор $R$ к $m-1$.
   3. Еще, $A_{m}\leq T$; набор $L$ к $m$.
3. Сейчас $L=R$, поиск завершен. Если $A_{L}=T$, возвращаться $L$. В противном случае поиск завершается как безуспешный.

Где 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

Дублирующиеся элементы

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

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

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

1. Набор $L$ к $0$ и $R$ к $n$.
2. Пока $L<R$,
   1. Набор $m$ (положение среднего элемента) пола до ${\frac {L+R}{2}}$, которое является наибольшим целым числом, меньшим или равным ${\frac {L+R}{2}}$.
   2. Если $A_{m}<T$, набор $L$ к $m+1$.
   3. Еще, $A_{m}\geq T$; набор $R$ к $m$.
3. Возвращаться $L$.

Если $L<n$ и $A_{L}=T$, затем $A_{L}$ это самый левый элемент, равный $T$. Даже если $T$ его нет в массиве, $L$ это ранг ​ $T$ в массиве или количество элементов в массиве, меньших $T$.

Где 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. Набор $L$ к $0$ и $R$ к $n$.
2. Пока $L<R$,
   1. Набор $m$ (положение среднего элемента) пола до ${\frac {L+R}{2}}$, которое является наибольшим целым числом, меньшим или равным ${\frac {L+R}{2}}$.
   2. Если $A_{m}>T$, набор $R$ к $m$.
   3. Еще, $A_{m}\leq T$; набор $L$ к $m+1$.
3. Возвращаться $R-1$.

Если $R>0$ и $A_{R-1}=T$, затем $A_{R-1}$ это самый правый элемент, равный $T$. Даже если $T$ его нет в массиве, $n-R$ количество элементов массива, превышающих $T$.

Где 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

Приблизительные совпадения

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

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

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

Производительность

Дерево , представляющее двоичный поиск. Здесь ищется массив $[20,30,40,50,80,90,100]$, а целевое значение $40$.

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

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

В худшем случае двоичный поиск делает ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ итерации цикла сравнения, где ${\textstyle \lfloor \cdot \rfloor }$ Обозначение обозначает функцию пола , которая дает наибольшее целое число, меньшее или равное аргументу, и ${\textstyle \log _{2}}$ это двоичный логарифм . Это связано с тем, что худший случай достигается, когда поиск достигает самого глубокого уровня дерева, и всегда есть ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ уровни в дереве для любого бинарного поиска.

Худший случай также может возникнуть, когда целевой элемент отсутствует в массиве. Если ${\textstyle n}$ на единицу меньше степени двойки, то это всегда так. В противном случае поиск может выполняться ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$итераций, если поиск достигает самого глубокого уровня дерева. Однако это может сделать ${\textstyle \lfloor \log _{2}(n)\rfloor }$ итераций, что на одну меньше, чем в худшем случае, если поиск заканчивается на втором по глубине уровне дерева.

В среднем, если предположить, что каждый элемент будет искаться с одинаковой вероятностью, двоичный поиск дает $\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$ итерации, когда целевой элемент находится в массиве. Это примерно равно $\log _{2}(n)-1$ итерации. Когда целевой элемент отсутствует в массиве, двоичный поиск выполняет $\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$ итераций в среднем, предполагая, что диапазон между и внешними элементами будет найден с одинаковой вероятностью.

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

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

Пространственная сложность

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

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

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

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

В представлении двоичного дерева успешный поиск может быть представлен путем от корня до целевого узла, называемым внутренним путем . Длина пути — это количество ребер (соединений между узлами), через которые проходит путь. Количество итераций, выполняемых поиском, при условии, что соответствующий путь имеет длину $l$, является $l+1$ считая начальную итерацию. Длина внутреннего пути — это сумма длин всех уникальных внутренних путей. Поскольку существует только один путь от корня до любого отдельного узла, каждый внутренний путь представляет собой поиск определенного элемента. Если есть $n$ элементы, которые являются положительным целым числом, а длина внутреннего пути равна $I(n)$, то среднее количество итераций для успешного поиска $T(n)=1+{\frac {I(n)}{n}}$, с добавлением одной итерации для подсчета начальной итерации.

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

$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor$

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

$\sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10$

Среднее количество итераций будет $1+{\frac {10}{7}}=2{\frac {3}{7}}$ на основе уравнения для среднего случая. Сумма за $I(n)$ можно упростить до:

$I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2$

Подставив уравнение для $I(n)$ в уравнение для $T(n)$:

$T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n$

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

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

Неудачные поиски можно представить, дополняя дерево внешними узлами , что образует расширенное двоичное дерево . Если внутренний узел или узел, присутствующий в дереве, имеет менее двух дочерних узлов, то добавляются дополнительные дочерние узлы, называемые внешними узлами, так что у каждого внутреннего узла есть два дочерних узла. Таким образом, неудачный поиск можно представить как путь к внешнему узлу, родителем которого является единственный элемент, оставшийся во время последней итерации. Внешний путь — это путь от корня к внешнему узлу. Длина внешнего пути представляет собой сумму длин всех уникальных внешних путей. Если есть $n$ элементы, которые являются положительным целым числом, а длина внешнего пути равна $E(n)$, то среднее количество итераций при неудачном поиске $T'(n)={\frac {E(n)}{n+1}}$, с добавлением одной итерации для подсчета начальной итерации. Длина внешнего пути делится на $n+1$ вместо $n$ потому что есть $n+1$ внешние пути, представляющие интервалы между элементами массива и за их пределами.

Эту задачу аналогичным образом можно свести к определению минимальной длины внешнего пути всех бинарных деревьев с $n$ узлы. Для всех двоичных деревьев длина внешнего пути равна длине внутреннего пути плюс $2n$. Подставив уравнение для $I(n)$:

$E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}$

Подставив уравнение для $E(n)$ в уравнение для $T'(n)$, средний случай неудачных поисков можно определить:

$T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)$

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

Каждая итерация процедуры двоичного поиска, определенной выше, выполняет одно или два сравнения, проверяя, равен ли средний элемент целевому элементу на каждой итерации. Предполагая, что каждый элемент будет найден с одинаковой вероятностью, каждая итерация выполняет в среднем 1,5 сравнения. Вариант алгоритма проверяет, равен ли средний элемент целевому элементу в конце поиска. В среднем это исключает половину сравнения на каждой итерации. Это немного сокращает время, затрачиваемое на итерацию на большинстве компьютеров. Однако он гарантирует, что поиск займет максимальное количество итераций, добавляя в среднем одну итерацию к поиску. Поскольку цикл сравнения выполняется только ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ раз в худшем случае небольшое увеличение эффективности на итерацию не компенсирует дополнительную итерацию для всех, кроме очень больших ${\textstyle n}$.

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

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

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

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

Сортированные массивы с двоичным поиском являются очень неэффективным решением, когда операции вставки и удаления чередуются с поиском, занимая ${\textstyle O(n)}$ время на каждую такую ​​операцию. Кроме того, отсортированные массивы могут усложнить использование памяти, особенно если в массив часто вставляются элементы. Существуют и другие структуры данных, которые поддерживают гораздо более эффективную вставку и удаление. Бинарный поиск можно использовать для выполнения точного сопоставления и установки членства (определения того, находится ли целевое значение в коллекции значений). Существуют структуры данных, которые поддерживают более быстрое точное сопоставление и набор членства. Однако, в отличие от многих других схем поиска, двоичный поиск можно использовать для эффективного приблизительного сопоставления, обычно выполняя такие сопоставления в ${\textstyle O(\log n)}$ время независимо от типа или структуры самих значений. Кроме того, есть некоторые операции, такие как поиск наименьшего и самого большого элемента, которые можно эффективно выполнять с отсортированным массивом.

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

Линейный поиск — это простой алгоритм поиска, который проверяет каждую запись, пока не найдет целевое значение. Линейный поиск может выполняться в связанном списке, что позволяет выполнять вставку и удаление быстрее, чем в массиве. Бинарный поиск в отсортированных массивах выполняется быстрее, чем линейный поиск, за исключением случаев, когда массив короткий, хотя массив необходимо отсортировать заранее. Все алгоритмы сортировки , основанные на сравнении элементов, такие как быстрая сортировка и сортировка слиянием , требуют как минимум ${\textstyle O(n\log n)}$ сравнения в худшем случае. В отличие от линейного поиска, двоичный поиск можно использовать для эффективного приблизительного сопоставления. Существуют такие операции, как поиск наименьшего и самого большого элемента, которые можно эффективно выполнить в отсортированном массиве, но не в несортированном.

Деревья

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

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

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

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

Хеширование

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

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

Проблема, связанная с поиском, — это членство в наборе . Любой алгоритм, выполняющий поиск, например двоичный поиск, также может использоваться для определения членства во множестве. Существуют и другие алгоритмы, которые более подходят для определения членства во множестве. Битовый массив является самым простым и полезен, когда диапазон ключей ограничен. Он компактно хранит набор битов , каждый бит представляет один ключ в диапазоне ключей. Битовые массивы работают очень быстро, требуя всего лишь ${\textstyle O(1)}$ время. типа Judy1 Массив Judy эффективно обрабатывает 64-битные ключи.

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

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

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

Вариации

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

Основная статья: Единый двоичный поиск

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

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

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

Основная статья: Экспоненциальный поиск

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

Экспоненциальный поиск расширяет двоичный поиск до неограниченных списков. Он начинается с поиска первого элемента с индексом, который равен степени двойки и превышает целевое значение. После этого он устанавливает этот индекс в качестве верхней границы и переключается на двоичный поиск. Поиск занимает ${\textstyle \lfloor \log _{2}x+1\rfloor }$ итераций до начала двоичного поиска и не более ${\textstyle \lfloor \log _{2}x\rfloor }$ итерации бинарного поиска, где ${\textstyle x}$ — это положение целевого значения. Экспоненциальный поиск работает с ограниченными списками, но становится улучшением по сравнению с бинарным поиском, только если целевое значение находится недалеко от начала массива.

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

Основная статья: Интерполяционный поиск

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

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

Распространенной функцией интерполяции является линейная интерполяция . Если $A$ это массив, $L,R$ — нижняя и верхняя границы соответственно, а $T$ является целью, то цель оценивается примерно $(T-A_{L})/(A_{R}-A_{L})$ пути между $L$ и $R$. При использовании линейной интерполяции и равномерном или близком к равномерному распределении элементов массива интерполяционный поиск делает ${\textstyle O(\log \log n)}$ сравнения.

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

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

Основная статья: Дробный каскадирование

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

Дробный каскад — это метод, который ускоряет двоичный поиск одного и того же элемента в нескольких отсортированных массивах. Для поиска каждого массива отдельно требуется ${\textstyle O(k\log n)}$ время, где ${\textstyle k}$ количество массивов. Дробный каскад сводит это к ${\textstyle O(k+\log n)}$ сохраняя в каждом массиве конкретную информацию о каждом элементе и его положении в других массивах.

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

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

Бинарный поиск был обобщен для работы с определенными типами графов, где целевое значение хранится в вершине, а не в элементе массива. Двоичные деревья поиска являются одним из таких обобщений: когда запрашивается вершина (узел) в дереве, алгоритм либо узнает, что вершина является целью, либо, в противном случае, в каком поддереве будет расположена цель. Однако это можно дополнительно обобщить как следующим образом: учитывая неориентированный, положительно взвешенный граф и целевую вершину, алгоритм при запросе вершины узнает, что она равна целевой, или ему дается инцидентное ребро, которое находится на кратчайшем пути от запрашиваемой вершины к цели. Стандартный алгоритм двоичного поиска — это просто случай, когда граф представляет собой путь. Аналогичным образом, в двоичных деревьях поиска ребра левого или правого поддерева задаются, когда запрашиваемая вершина не равна целевой. Для всех неориентированных графов с положительными весами существует алгоритм, который находит целевую вершину в $O(\log n)$ запросы в худшем случае.

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

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

Алгоритмы двоичного поиска с шумом решают случай, когда алгоритм не может надежно сравнить элементы массива. Для каждой пары элементов существует определенная вероятность того, что алгоритм выполнит неправильное сравнение. Шумный двоичный поиск может найти правильное положение цели с заданной вероятностью, которая контролирует надежность полученного положения. Любая процедура двоичного поиска с шумом должна производить как минимум $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ сравнения в среднем, где $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ - двоичная функция энтропии и $\tau$ — это вероятность того, что процедура даст неправильную позицию. Зашумленную задачу бинарного поиска можно рассматривать как случай игры Реньи-Улама : вариант « Двадцати вопросов», ответы на которые могут быть неправильными.

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

Классические компьютеры ограничены наихудшим случаем ровно ${\textstyle \lfloor \log _{2}n+1\rfloor }$ итерации при выполнении двоичного поиска. Квантовые алгоритмы бинарного поиска по-прежнему ограничены частью ${\textstyle \log _{2}n}$ запросы (представляющие итерации классической процедуры), но постоянный коэффициент меньше единицы, что обеспечивает меньшую временную сложность на квантовых компьютерах . Любая точная процедура квантового двоичного поиска, то есть процедура, которая всегда дает правильный результат, требует как минимум ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ запросы в худшем случае, где ${\textstyle \ln }$ это натуральный логарифм . Существует точная процедура квантового двоичного поиска, которая работает в ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ запросы в худшем случае. Для сравнения, алгоритм Гровера является оптимальным квантовым алгоритмом для поиска неупорядоченного списка элементов и требует $O({\sqrt {n}})$ запросы.

История

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

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

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

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

— Дональд Кнут

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

В практической реализации переменные, используемые для представления индексов, часто имеют фиксированный размер (целые числа), и это может привести к арифметическому переполнению для очень больших массивов. Если середина пролета рассчитывается как ${\frac {L+R}{2}}$, то значение $L+R$ может превышать диапазон целых чисел типа данных, используемого для хранения средней точки, даже если $L$ и $R$ находятся в пределах диапазона. Если $L$ и $R$ неотрицательны, этого можно избежать, вычислив среднюю точку как $L+{\frac {R-L}{2}}$.

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

Библиотечная поддержка

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

• C предоставляет функцию bsearch() в своей стандартной библиотеке , которая обычно реализуется посредством двоичного поиска, хотя официальный стандарт этого не требует.
• C++ предоставляет Стандартная библиотека функции binary_search(), lower_bound(), upper_bound() и equal_range().
• D Phobos, в Стандартная библиотека std.range модуль предоставляет тип SortedRange (возвращено sort() и assumeSorted() функции) с методами contains(), equaleRange(), lowerBound() и trisect(), которые по умолчанию используют методы двоичного поиска для диапазонов, предлагающих произвольный доступ.
• КОБОЛ предоставляет SEARCH ALL глагол для выполнения двоичного поиска в упорядоченных таблицах COBOL.
• Иди ​ sort пакет стандартной библиотеки содержит функции Search, SearchInts, SearchFloat64s, и SearchStrings, которые реализуют общий двоичный поиск, а также специальные реализации для поиска фрагментов целых чисел, чисел с плавающей запятой и строк соответственно.
• Java предлагает набор перегруженных binarySearch() статические методы в классах Arrays и Collections в стандарте java.util пакет для выполнения двоичного поиска в массивах Java и на Listс соответственно.
• 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 Array включает в себя Класс bsearch метод со встроенным приближенным сопоставлением.
• Rust обеспечивает Примитив среза binary_search(), binary_search_by(), binary_search_by_key(), и partition_point().

См. также

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

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

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

Источники

• Бентли, Джон (2000). Перлы программирования (2-е изд.). Аддисон-Уэсли . ISBN  978-0-201-65788-3 .
• Баттерфилд, Эндрю; Нгонди, Джерард Э. (2016). Словарь информатики (7-е изд.). Оксфорд, Великобритания: Издательство Оксфордского университета . ISBN  978-0-19-968897-5 .
• Чанг, Ши-Куо (2003). Структуры данных и алгоритмы . Программная инженерия и инженерия знаний. Том. 13. Сингапур: World Scientific . ISBN  978-981-238-348-8 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009). Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN  978-0-262-03384-8 .
• Фицджеральд, Майкл (2015). Рубиновый карманный справочник . Севастополь, Калифорния: O'Reilly Media . ISBN  978-1-4919-2601-7 .
• Голдман, Салли А .; Голдман, Кеннет Дж. (2008). Практическое руководство по структурам данных и алгоритмам с использованием Java . Бока-Ратон, Флорида: CRC Press . ISBN  978-1-58488-455-2 .
• Касахара, Масахиро; Моришита, Шиничи (2006). Масштабная обработка последовательности генома . Лондон, Великобритания: Издательство Имперского колледжа. ISBN  978-1-86094-635-6 .
• Кнут, Дональд (1997). Фундаментальные алгоритмы . Искусство компьютерного программирования . Том. 1 (3-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN  978-0-201-89683-1 .
• Кнут, Дональд (1998). Сортировка и поиск . Искусство компьютерного программирования . Том. 3 (2-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN  978-0-201-89685-5 .
• Кнут, Дональд (2011). Комбинаторные алгоритмы . Искусство компьютерного программирования . Том. 4А (1-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN  978-0-201-03804-0 .
• Моффат, Алистер; Терпин, Эндрю (2002). Алгоритмы сжатия и кодирования . Гамбург, Германия: Академическое издательство Kluwer. дои : 10.1007/978-1-4615-0935-6 . ISBN  978-0-7923-7668-2 .
• Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Река Аппер-Сэддл, Нью-Джерси: Addison-Wesley Professional. ISBN  978-0-321-57351-3 . Сокращенная веб-версия ; книжная версия .
• Страуструп, Бьярне (2013). Язык программирования C++ (4-е изд.). Река Аппер-Сэддл, Нью-Джерси: Addison-Wesley Professional. ISBN  978-0-321-56384-2 .

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

• Словарь алгоритмов и структур данных NIST: двоичный поиск
• Сравнения и тесты различных реализаций двоичного поиска на C. Архивировано 25 сентября 2019 г. на Wayback Machine.