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

Алгоритм поиска, положение целевого значения в отсортированном массиве

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

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

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

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

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

• 1 Алгоритм
  • 1.1 Процедура
    • 1.1.1 Альтернативная процедура
  • 1.2 Дублирующиеся элементы
    • 1.2.1 Процедура поиска крайнего левого элемента
    • 1.2.2 Процедура поиска крайний правый элемент
  • 1.3 Приблизительные совпадения
• 2 Производительность
  • 2.1 Сложность пространства
  • 2.2 Выведение среднего значения
    • 2.2.1 Успешные поиски
    • 2.2.2 Неудачные поиски
    • 2.2.3 Производительность альтернативной процедуры
  • 2.3 Время выполнения и использования кеша
• 3 Двоичный поиск по сравнению с другими схемами
  • 3.1 Линейный поиск
  • 3.2 Деревья
  • 3.3 Хеширование
  • 3.4 Установка алгоритмов членства
  • 3.5 Другие данные структуры
• 4 Варианты
  • 4.1 Единый двоичный поиск
  • 4.2 Экспоненциальный поиск
  • 4.3 Интерполяционный поиск
  • 4.4 Дробное каскадирование
  • 4.5 Обобщение на графы
  • 4.6 Шумный двоичный поиск
  • 4.7 Квантовый двоичный поиск
• 5 История
• 6 Проблемы реализации
• 7 Поддержка библиотек еки
• 8 См. также
• 9 Примечания и ссылки
  • 9.1 Примечания
  • 9.2 Цитаты
  • 9.3 Работает
• 10 Внешние ссылки

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

Процедура

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

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

Эта итерационная процедура отслеживает границы поиска с двумя переменными $L\; \{\backslash \; displaystyle\; L\}$и $R\; \{\backslash \; displaystyle\; R\}$. Процедура может быть выражена в псевдокоде следующим образом, где имена и параметры остаются такими же, как указано выше, floor- это функция пола, а неудачныйотносится к конкретное значение, которое сообщает об ошибке поиска.

функция binary_search (A, n, T) равно L: = 0 R: = n - 1, а L ≤ R до m : = этаж ((L + R) / 2) если A [m] T, то R: = m - 1 else : return m return неудачно

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

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

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

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

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

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

function binary_search_alternative (A, n, T) is L: = 0 R: = n - 1 в то время как L! = R do m: = ceil ((L + R) / 2) если A [m]>T тогда R: = m - 1 else : L: = m если A [L] = T, то return L return неудачный

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

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

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

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

1. Установить для $L\; \{\backslash \; displaystyle\; L\}$значение $0\; \{\backslash \; displaystyle\; 0\}$и $R\; \{\backslash \; displaystyle\; R\}$до $n\; \{\backslash \; displaystyle\; n\}$.
2. Пока ,
   1. Установить $m\; \{\backslash \; displaystyle\; m\}$(положение среднего элемента) до этажа из $L\; +\; R\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{L\; +\; R\}\; \{2\}\}\}$, наибольшее целым числом, меньшим или равным $L\; +\; R\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{L\; +\; R\}\; \{2\}\}\}$.
   2. Если , установить $L\; \{\backslash \; displaystyle\; L\}$на $m\; +\; 1\; \{\backslash \; displaystyle\; m\; +\; 1\}$.
   3. Else, $A\; m\; \ge \; T\; \{\backslash \; Displaystyle\; A\_\; \{m\; \}\; \backslash \; geq\; T\}$; установить $R\; \{\backslash \; displaystyle\; R\}$на $m\; \{\backslash \; displaystyle\; m\}$.
3. Возврат $L\; \{\backslash \; displaystyle\; L\}$.

Если и $AL\; =\; T\; \{\backslash \; displaystyle\; A\_\; \{L\}\; =\; T\}$, тогда $AL\; \{\backslash \; displaystyle\; A\_\; \{L\}\}$- крайний левый элемент, равный $T\; \{\; \backslash \; Displaystyle\; T\}$. Даже если $T\; \{\backslash \; displaystyle\; T\}$отсутствует в массиве, $L\; \{\backslash \; displaystyle\; L\}$будет ранг из $T\; \{\; \backslash \; displaystyle\; T\}$в массиве, или количество элементов в массиве, которые меньше $T\; \{\backslash \; displaystyle\; T\}$.

где floor- функция пола, псевдокод для версии:

функция двоичный_поиск крайний левый (A, n, T): L: = 0 R: = n в то время как L < R: m := floor((L + R) / 2) ifA [m] 
Процедура поиска крайнего правого элемента
Чтобы найти крайний правый элемент, можно использовать следующие функции:
Установить $L\; \{\backslash \; displaystyle\; L\}$на $0\; \{\backslash \; displaystyle\; 0\}$и $R\; \{\backslash \; displaystyle\; R\}$в $n\; \{\backslash \; displaystyle\; n\; \}$.
Пока , 
Установить $m\; \{\backslash \; displaystyle\; m\}$(положение среднего элемента) на этаж из $L\; +\; R\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{L\; +\; R\}\; \{2\}\}\}$, является наибольшим целым числом, меньшим или р авным $L\; +\; R\; 2\; \{\backslash \; отображает\; tyle\; \{\backslash \; frac\; \{L\; +\; R\}\; \{2\}\}\}$.
Если $A\; m>T\; \{\backslash \; displaystyle\; A\_\; \{m\}>T\}$, установить $R\; \{\backslash \; displaystyle\; R\}$до $m\; \{\backslash \; displaystyle\; m\}$.
Else, $A\; m\; \le \; T\; \{\backslash \; displaystyle\; A\_\; \{m\}\; \backslash \; leq\; T\}$; установить $L\; \{\backslash \; displaystyle\; L\}$на $m\; +\; 1\; \{\backslash \; displaystyle\; m\; +\; 1\}$.
Return $R\; -\; 1\; \{\backslash \; displaystyle\; R-1\}$.
Если $L>0\; \{\backslash \; displaystyle\; L>0\}$и $AR\; -\; 1\; =\; T\; \{\backslash \; displaystyle\; A\_\; \{R-1\}\; =\; T\}$, $AR\; -\; 1\; \{\backslash \; displaystyle\; A\_\; \{R-1\}\}$- крайний правый элемент, равный $T\; \{\backslash \; displaystyle\; T\}$. Даже если $T\; \{\backslash \; displaystyle\; T\}$отсутствует в массиве, $n\; -\; R\; +\; 1\; \{\backslash \; displaystyle\; nR\; +\; 1\}$- количество элементов в массиве, превышающих $T\; \{\backslash \; displaystyle\; T\}$.
Где этаж- функция пола, псевдокод для этой версии:
функция binary_search_rightmost (A, n, T): L: = 0 R: = n while L < R: m := floor((L + R) / 2) ifA [m]>T : R: = m else : L: = m + 1 return R - 1
Приблизительные совпадения
  Двоичный поиск может б ыть адаптирован для вычислений Ближайшие матчи. В приведенном выше примере ранг, предшественник, преемник и ближайший сосед показаны для целевого $5\; \{\backslash \; displaystyle\; 5\}$, которого нет в массиве. 
Вышеупомянутая процедура выполняет только точные совпадения, находя цель целевого значения. Возможный поиск работает с отсортированными типами. Например, двоичный поисковый элемент для выбора данного значения его ранга (количество меньших элементов), предшественника (следующий наименьший элемент), преемника (следующий наибольший элемент) и ближайший сосед. Запросы диапазона, ищущие количество элементов между двумя значениями, которые возникают с помощью двух запросов ранжирования.
Запросы ранжирования экспериментов с помощью процедур для поиска крайнего левого элемента. Число элементов меньше целевого значения возвращается процедурой.
Запросы предшественников продукты с запросами ранжирования. Если ранг целевого значения равен $r\; \{\backslash \; displaystyle\; r\}$, его предшественник равен $r\; -\; 1\; \{\backslash \; displaystyle\; r-1\}$.
Для запросов преемников можно использовать поиск крайнего правого элемента. Если результатом выполнения процедуры для целевого значения является $r\; \{\backslash \; displaystyle\; r\}$, то преемником целевого значения является $r\; +\; 1\; \{\backslash \; displaystyle\; r\; +\; 1\}$.
Ближайшим соседом целевого значения его предшественник или преемник, в зависимости от того, что ближе.
Запросы диапазона также просты. Как только ранги двух известны, количество элементов, больше или равных первому значению и меньше второго, является разницей между двумя рангами. Этот счетчик может быть увеличен или уменьшен на единицу в зависимости от того, следует ли считать конечные точки диапазона части и содержат ли массив записи, соответствующие этим конечным точкам.
Производительность
  A дерево, представляющее двоичное поиск. Здесь выполняется поиск в массиве $[20,\; 30,\; 40,\; 50,\; 80,\; 90,\; 100]\; \{\backslash \; displaystyle\; [20,30,40,50,80,90,100]\}$, а целевое значение : $40\; \{\backslash \; displaystyle\; 40\}$.  Наихудший случай достигается, когда поиск достигает самого глубокого уровня дерева, в то время как лучший случай достигается, когда целевым является средний элемент. 
В точки зрения количества возможностей двоичного поиска можно проанализировать, выполнить процедуры в двоичном дереве. Корневой узел дерева - это средний элемент массива. Средний элемент нижней половины является левым дочерним узлом корня, средний элемент верхней половины является правым дочерним узлом корня. Остальная часть дерева построена аналогичным образом. Текущий с корневого узла, выполняется обход левого или правого поддеревья в зависимости от того, является ли целевое значение меньше или больше, чем рассматриваемый узел.
В худшем случае двоичный поиск составляет $\lfloor \; log\; 2\; \; (n)\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; +1\; \backslash \; rfloor\}$итераций цикла сравнения, где $\lfloor \; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; rfloor\}$обозначает функцию floor, которая возвращает наибольшее целое число, меньшее или равное аргумент, а $log\; 2\; \{\backslash \; textstyle\; \backslash \; log\; \_\; \{2\}\}$- это двоичный логарифм. Это потому, что наихудший случай достигается, когда достигается самого глубокого уровня дерева, и всегда есть $\lfloor \; log\; 2\; \; (n)\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; +1\; \backslash \; rfloor\; \}$уровни в дереве для любого бинарного поиска.
Наихудший случай также может быть достигнут, когда целевой элемент отсутствует в массиве. Если $n\; \{\backslash \; textstyle\; n\}$на единицу меньше степени двойки, то это всегда так. В противном случае поиск может выполнить $\lfloor \; log\; 2\; \; (n)\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; +1\; \backslash \; rfloor\}$итераций, если поиск достигнет самый глубокий уровень дерева. Однако он может сделать $\lfloor \; log\; 2\; \; (n)\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\}$итераций, что на единицу меньше, чем в худшем случае, если поиск заканчивается на втором по глубине уровне дерева.
В среднем, предположить, что поиск каждого элемента одинаков, бинарный поиск составляет $\lfloor \; log\; 2\; \; (n)\; \rfloor \; +\; 1\; -\; (2\; \lfloor \; журнал\; 2\; \; (N)\; \rfloor \; +\; 1\; -\; \lfloor \; журнал\; 2\; \; (N)\; \rfloor \; -\; 2)\; /\; N\; \{\backslash \; Displaystyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +\; 1-\; (2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +1\}\; -\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; -2)\; /\; n\}$итераций, когда целевой элемент находится в массиве. Это приблизительно равно $log\; 2\; \; (n)\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; log\; \_\; \{2\}\; (n)\; -1\}$итераций. Когда объект элемент отсутствует в массиве, двоичный поиск выполняет $\lfloor \; log\; 2\; \; (n)\; \rfloor \; +\; 2-2\; \lfloor \; log\; 2\; \; (n)\; \rfloor \; +\; 1\; /\; (n\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{\; 2\}\; (n)\; \backslash \; rfloor\; +\; 2-2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +1\}\; /\; (n\; +\; 1)\}$итераций в среднем, предполагая что диапазон между и внешними элементами с одинаковой вероятностью будет найден.
В лучшем случае, когда целевым значением является средний размер элемента, его позиция после одной итерации.
Что касается итераций, ни один алгоритм поиска, который работает только путем сравнения элементов, не может показать лучшую среднюю и худшую показатели, чем двоичный поиск. Дерево сравнивает, представляет двоичный поиск, минимально возможное количество уровней, поскольку каждый уровень выше самого нижнего уровня заполнен полностью. В случае алгоритма поиска может исключить несколько элементов в итерации, увеличивая итераций, необходимых в среднем и худшем случае. Так обстоит дело с другими алгоритмами поиска, основанными на сравнении, поскольку они могут работать быстрее с некоторыми целевыми значениями, средняя производительность по всем элементам хуже, чем у двоичного поиска. Разделив массив пополам, двоичный поиск гарантирует, что размер обоих подмассивов будет как можно более схожим.
Сложность пространства
Для двоичного поиска требуются три указателя на элементы, которые могут быть индексами памяти или указатели на ячейки, независимо от размера массива. Следовательно, пространственная сложность двоичного поиска составляет $O\; (1)\; \{\backslash \; displaystyle\; O\; (1)\}$в модели вычислений Word RAM.
Выведение среднего случая
Среднее количество итераций,Выполняемые двоичным поиском, зависит от вероятности поиска каждого элемента. Средний случай отличается для успешных поисков и неудачных поисков. Предполагается, что каждый элемент с одинаковой вероятностью будет подвергнут успешному поиску. Для безуспешных поисков, что с одинаковой вероятностью будут найдены интервалы  между и внешними элементами. Средний случай успешного поиска - это количество итераций, необходимых для поиска каждого элемента ровно один раз, деленное на $n\; \{\backslash \; displaystyle\; n\}$, количество элементов. Средний случай неудачного поиска - это количество итераций, необходимое для поиска элемента в каждом интервале ровно один раз, деленное на интервалы $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$.
Успешные поиски
В представлении двоичного дерева успешный поиск может быть представлен путем от корня до целевого узла, который называется внутренним путем. Длина пути - это количество ребер соединений между узлами, через которые проходит путь. Количество итераций, выполненных поиском, с учетом того, что соответствующий путь имеет длину $l\; \{\backslash \; displaystyle\; l\}$, составляет $l\; +\; 1\; \{\backslash \; displaystyle\; l\; +\; 1\}$с учетом начальной итерации. Длина внутреннего пути - это сумма длин всех уникальных внутренних путей. Существует только один путь от корня до любого отдельного узла, каждый внутренний путь представляет собой поиск определенного элемента. Если есть $n\; \{\backslash \; displaystyle\; n\}$элементов, которое является положительным целым числом, и длина внутреннего пути равна $I\; (n)\; \{\backslash \; displaystyle\; I\; (n)\}$, тогда среднее количество итераций для успешного поиска $T\; (n)\; =\; 1\; +\; I\; (n)\; n\; \{\backslash \; displaystyle\; T\; (n)\; =\; 1\; +\; \{\backslash \; frac\; \{I\; (n)\}\; \{n\}\}\}$, с добавлением одной итерации для подсчета начальной итерации.
Бинарный поиск является оптимальным алгоритмом поиска со сравнениями, эта проблема сводится к вычислению минимальной длины внутреннего пути всех бинарных деревьев с узлами $n\; \{\backslash \; displaystyle\; n\}$, что равно:
$я\; (п)\; =\; \sum \; К\; знак\; равно\; 1\; N\; \lfloor \; журнал\; 2\; \; (к)\; \rfloor \; \{\backslash \; displaystyle\; I\; (n)\; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; \backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (k)\; \backslash \; right\; below\; \backslash \; rfloor\}$
Например, в массиве из 7 элементов root требует одной и четыретерации, два элемента root требуют двух итераций, а элемент ниже требует трех итераций. В этом случае длина внутреннего пути равна:
$\sum \; k\; =\; 1\; 7\; \lfloor \; log\; 2\; \; (k)\; \rfloor \; =\; 0\; +\; 2\; (1)\; +\; 4\; (2)\; =\; 2\; +\; 8\; =\; 10\; \{\backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{7\}\; \backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (k)\; \backslash \; right\; \backslash \; rfloor\; =\; 0\; +\; 2\; (1)\; +4\; (2)\; =\; 2\; +\; 8\; =\; 10\}$
Среднее количество итераций будет $1\; +\; 10\; 7\; =\; 2\; 3\; 7\; \{\backslash \; displaystyle\; 1\; +\; \{\backslash \; frac\; \{10\}\; \{7\}\}\; =\; 2\; \{\backslash \; frac\; \{3\}\; \{7\}\}\}$на основе уравнений для среднего случая. Сумма для $I\; (n)\; \{\backslash \; displaystyle\; I\; (n)\}$может быть упрощена до:
$I\; (n)\; =\; \sum \; k\; =\; 1\; n\; \lfloor \; log\; 2\; \; (k)\; \rfloor \; знак\; равно\; (N\; +\; 1)\; \lfloor \; журнал\; 2\; \; (N\; +\; 1)\; \rfloor \; -\; 2\; \lfloor \; журнал\; 2\; \; (N\; +\; 1)\; \rfloor \; +\; 1\; +\; 2\; \{\backslash \; Displaystyle\; I\; (п)\; =\; \backslash \; сумма\; \_\; \{к\; =\; 1\}\; ^\; \{\; n\}\; \backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (k)\; \backslash \; right\; \backslash \; rfloor\; =\; (n\; +\; 1)\; \backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; -2\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; +1\}\; +2\}$
Подставляем уравнение для $I\; (n)\; \{\backslash \; displaystyle\; I\; (n)\}$в уравнение для $T\; (n)\; \{\backslash \; displaystyle\; T\; (n)\}$:
$T\; (n)\; =\; 1\; +\; (n\; +\; 1)\; \lfloor \; журнал\; 2\; \; (n\; +\; 1)\; \rfloor \; -\; 2\; \lfloor \; журнал\; 2\; \; (\; n\; +\; 1)\; \rfloor \; +\; 1\; +\; 2\; n\; =\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 1\; -\; (2\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 1\; -\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; -\; 2)\; /\; n\; \{\backslash \; Стиль\; отображения\; Т\; (п)\; =\; 1\; +\; \{\backslash \; гидроразрыва\; \{(п\; +\; 1)\; \backslash \; влево\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; -2\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; +1\}\; +2\}\; \{n\}\}\; =\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +\; 1-\; (2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\})\; (\; n)\; \backslash \; rfloor\; +1\}\; -\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (\; n)\; \backslash \; rfloor\; -2)\; /\; n\}$
Для целых $n\; \{\backslash \; displaystyle\; n\}$это эквивалентно уравнению для среднего возраста при успешном поиске, соответствующем выше.
Неудачный поиск
Неудачный поиск может быть представлен путем добавления в дерево внешних узлов, которые образуют расширенное двоичное дерево. Если внутренний узел или узел, присутствующий в дереве, имеет менее двух дочерних узлов, то добавляются дополнительные дочерние узлы, называемые внешними узлами, так что каждый внутренний узел имеет двух дочерних узлов. Таким образом, неудачный поиск может быть представлен как путь к внешнему узлу, основным элементом которого является единственный элемент, оставшийся во время последней итерации. Внешний путь - это путь от корня к внешнему узлу. Длина внешнего пути - это сумма длин всех уникальных внешних путей. Если есть элементы $n\; \{\backslash \; displaystyle\; n\}$, которое является положительным целым числом, и длина внешнего пути равна $E\; (n)\; \{\backslash \; displaystyle\; E\; (n)\}$, тогда среднее количество итераций для безуспешного поиска $T\; \prime \; (n)\; =\; E\; (n)\; n\; +\; 1\; \{\backslash \; displaystyle\; T\; \text{'}(n)\; =\; \{\backslash \; frac\; \{E\; (n)\}\; \{n\; +1\}\}\}$, с добавлением одной итерации для подсчета начальной итерации. Длина внешнего пути делится на $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$вместо $n\; \{\backslash \; displaystyle\; n\}$, потому что есть $n\; +\; 1\; \{\backslash \; displaystyle\; n\; +\; 1\}$внешние пути, представляющие внутренние элементы между элементами массива и вне их.
Эту проблему можно аналогичным образом свести к определению минимальной длины внешнего пути все двоичные деревья с узлами $n\; \{\backslash \; displaystyle\; n\}$. Для всех двоичных деревьев длина внешнего пути равна длине внутреннего пути плюс $2\; n\; \{\backslash \; displaystyle\; 2n\}$. Подставляя уравнение для $I\; (n)\; \{\backslash \; displaystyle\; I\; (n)\}$:
$E\; (n)\; =\; I\; (n)\; +\; 2\; n\; =\; [(n\; +\; 1)\; \lfloor \; log\; 2\; \; (n\; +\; 1)\; \rfloor \; -\; 2\; \lfloor \; журнал\; 2\; \; (n\; +\; 1)\; \rfloor \; +\; 1\; +\; 2]\; +\; 2\; n\; =\; (n\; +\; 1)\; (\lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 2)\; -\; 2\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 1\; \{\backslash \; Displaystyle\; E\; (N)\; =\; I\; (N)\; +\; 2n\; =\; \backslash \; left\; [(n\; +\; 1)\; \backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; -2\; ^\; \{\backslash \; left\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n\; +\; 1)\; \backslash \; right\; \backslash \; rfloor\; +1\}\; +2\; \backslash \; right]\; +\; 2n\; =\; (n\; +\; 1)\; (\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +2)\; -\; 2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +1\}\}$
Подставляя уравнение для $E\; (n)\; \{\backslash \; displaystyle\; E\; (n)\}$в уравнение для $T\; \prime \; (n)\; \{\backslash \; displaystyle\; T\; \text{'}(n)\}$, можно определить средний случай неудачных поисков:
$T\; \prime \; (n)\; =\; (n\; +\; 1)\; (\lfloor \; журнал\; 2\; \; (\; n)\; \rfloor \; +\; 2)\; -\; 2\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 1\; (n\; +\; 1)\; =\; журнал\; 2\; \; (n)\; \rfloor \; +\; 2-2\; \lfloor \; журнал\; 2\; \; (n)\; \rfloor \; +\; 1\; /\; (n\; +\; 1)\; \{\backslash \; displaystyle\; T\; \text{'}(n)\; =\; \{\backslash \; frac\; \{(n\; +\; 1)\; (\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +2)\; -2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (\; n)\; \backslash \; rfloor\; +1\}\}\; \{(n\; +\; 1)\}\}\; =\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +\; 2-2\; ^\; \{\backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; \backslash \; rfloor\; +1\}\; /\; (n\; +\; 1)\}$
Выполнение альтернативной процедуры
Каждая итерация процедуры двоичного поиска, указанным выше, одно действует или два сравнения, проверяя, равен ли средний элемент целевому на каждой итерации. Предполагается, что вероятность поиска каждого элемента одинакова, на каждой итерации выполняется 1,5 сравнения. Вариант алгоритма проверяет, равенство ли средний элемент целевому в конце поиска. В среднем это исключает половину сравнения из каждой итерации. Это немного сокращает время, затрачиваемое на одну итерацию на большинстве компьютеров. Однако это гарантирует, что поиск максимального количества итераций, в среднем добавляя одну итерацию к поиску. Цикл выполнения выполняется только $\lfloor \; log\; 2\; \; (n)\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; (n)\; +1\; \backslash \; rfloor\}$раз в худшем случае, небольшое повышение эффективности на итерацию не компенсирует лишнюю итерацию для всех, кроме очень больших $n\; \{\backslash \; textstyle\; n\}$.
Время выполнения и использования кеша
При анализе производительности двоичного поиска, еще одно соображение - время, необходимое для сравнение двух элементов. Для больших чисел и больших время увеличивается линейно по мере увеличения длины кодирования (обычно числа бит ) элементов. Например, сравнение пары 64-битных целых чисел без знака потребует сравнение до удвоения битов по сравнению с парой 32-битных целых чисел без знака. Худший случай достигается, когда целые числа равны. Это может быть значительным, когда длина кодирования элементов велики, например, с большими типами строк или длинными строками, что делает сравнение элементов дорогим. Более того, сравнение значений с плавающей запятой (наиболее распространенное цифровое представление действительных чисел ) часто бывает дороже, чем сравнение целых чисел или коротких строк.
На большинстве компьютерных архитектурных процессоров  имеетный кэш, отдельный от RAM. Они размещены в самом процессоре, кеши доступны намного быстрее, но обычно они размещены гораздо меньше, чем ОЗУ. Следовательно, большинство процессоров памяти, к которым был осуществлен доступ недавно, вместе с ячейками памяти, близкими к ним. Например, когда осуществляется доступ к элементу массива, сам элемент может храниться вместе с элементами, которые ускоряются последовательный доступ к элементу массива, близким по индексу к другу (местоположение ссылки ). В отсортированном массиве двоичный поиск может перейти к удаленным ячейкам памяти, если массив большой, в отличие от алгоритмов (как линейный поиск и линейный поиск в хэш-таблицах ), которые последовательно обращаются к элементам. Это немного увеличивает время выполнения двоичного поиска больших массивов в большинстве систем.
Сравнение двоичного поиска с другими схемами
Отсортированные массивы с двоичным поиском являются очень неэффективным решением, когда операции вставки и удаление чередуется с поиском, занимая $O\; (n)\; \{\backslash \; textstyle\; O\; (\; n)\}$раз для каждой такой операции. Кроме того, отсортированные массивы могут усложнить использование памяти, особенно когда элементы часто вставляются в массив. Существуют и другие структуры, которые намного более эффективную вставку и удаление. Двоичный поиск месторасположения для выполнения точного сопоставления и установки члена (определения того, находится ли целевое значение в наборе). Существуют структуры данных, которые включают быстрое быстрое соответствие и набор членов. Однако, отличие от многих других схем, двоичный поиск может найти подходящее сопоставление, выполняя такие сопоставления в $O\; (log\; \; n)\; \{\backslash \; textstyle\; O\; (\backslash \; log\; n)\}$времени независимо от типа или структуры любого значения. Кроме того, есть некоторые операции, такие как поиск наименьшего и наивысшего элемента, которые могут быть выполнены в отсортированном массиве.
Линейный поиск
Линейный поиск - это простой алгоритм поиска, который проверяет каждую запись, пока не будет найдено целевое значение. Линейный поиск может работать в связанном списке, что позволяет выполнять вставку и удаление быстрее, чем в массиве. Двоичный поиск выполняется быстрее, чем линейный поиск для отсортированных массивов, за исключением случаев, когда массив короткий, хотя приведенный массив отсортировать короткий. Все алгоритмы сортировки, основанные на сравнении элементов, такие как quicksort и сортировка слиянием, требуют не менее $O\; (n\; log\; \; n)\; \{\backslash \; textstyle\; O\; (n\; \backslash \; log\; n)\}$сравнение в худшем случае. В линейного поиска, познакомительный поиск местная инстанция для приблизительного сопоставления. Существуют такие операции, как поиск наименьшего и наибольшего элемента, которые могут быть эффективно выполнены в отсортированном массиве, но не в несортированном массиве.
Деревья
  Двоичные деревья поиска ищутся с использованием алгоритма, аналогичного двоичный поиск. 
A двоичное дерево поиска представляет собой структуру данных двоичного дерева, которая работает на основе принципа двоичного поиска. Записи в дереве упорядочены в отсортированном порядке, и каждая запись в дереве может быть найдена с использованием алгоритма, аналогичного бинарному поиску, который занимает среднее логарифмическое время. Вставка и удаление также требуют среднего логарифмического времени в двоичных деревьях поиска. Это может быть быстрее, чем линейная вставка и удаление отсортированных массивов, а двоичные деревья сохраняют способность выполнять все возможные операции с отсортированным массивом, включая диапазон и приблизительные запросы.
Однако двоичный поиск обычно более эффективен для поиска, поскольку деревья двоичного поиска, скорее всего, будут несовершенно сбалансированы, что приведет к немного худшей производительности, чем двоичный поиск. Это даже применимо к сбалансированным двоичным деревьям поиска, двоичным деревьям поиска, которые балансируют свои собственные узлы, потому что они редко создают дерево с наименьшим возможным уровнем. За исключением сбалансированных двоичных деревьев поиска, дерево может быть сильно несбалансированным с несколькими внутренними узлами с двумя дочерними элементами, в результате чего среднее и худшее время поиска приближается к сравнениям $n\; \{\backslash \; textstyle\; n\}$. Деревья двоичного поиска занимают больше места, чем отсортированные массивы.
Деревья двоичного поиска поддаются быстрому поиску во внешней памяти, хранящейся на жестких дисках, поскольку деревья двоичного поиска могут быть эффективно структурированы в файловых системах. B-дерево обобщает этот метод организации дерева. B-деревья часто используются для организации долговременного хранения, например, баз данных и файловых систем.
Хеширование
Для реализации ассоциативных массивов, хэш-таблицы, структура данных, которая отображает ключи в записи с использованием хэш-функции , как правило, быстрее, чем двоичный поиск по отсортированному массиву записей. Большинство реализаций хеш-таблиц в среднем требуют только амортизированного постоянного времени. Однако хеширование бесполезно для приблизительных совпадений, таких как вычисление следующего наименьшего, следующего наибольшего и ближайшего ключей, поскольку единственная информация, предоставляемая при неудачном поиске, - это то, что цель отсутствует ни в одной записи. Для таких совпадений идеально подходит двоичный поиск, выполняющий их за логарифмическое время. Двоичный поиск также поддерживает приблизительные совпадения. Некоторые операции, такие как поиск наименьшего и наибольшего элемента, можно эффективно выполнять с отсортированными массивами, но не с хеш-таблицами.
Установить алгоритмы членства
Связанная проблема с поиском - установить членство. Любой алгоритм, который выполняет поиск, например двоичный поиск, также может использоваться для определения членства. Там другие алгоритмы, которые более подходят для членства в множестве. Битовый массив  - простой, полезный, когда диапазон самый ограничен. Он компактно хранит набор из битов, где каждый бит представляет отдельный ключ в диапазоне ключей. Битовые массивы работают очень быстро и требуют всего $O\; (1)\; \{\backslash \; textstyle\; O\; (1)\}$времени. Тип Judy1 Массив Judy эффективно обрабатывает 64-битные ключи.
Для приблизительных результатов фильтры Блума, другая вероятностная структура данных, основанная на хешировании, хранят установить ключи путем кодирования ключей с использованием битового массива и нескольких хэш-функций. Фильтры Блума в большинстве случаев занимают гораздо меньше места, чем битовые массивы, и ненамного медленного: с хэш-функциями $k\; \{\backslash \; textstyle\; k\}$запросы членства требуют только $O\; (k)\; \{\backslash \; textstyle\; O\; (k)\}$время. Блума страдают от ложных срабатываний.
Другие структуры данных
Существуют фильтры данных, которые могут улучшить двоичный поиск в некоторых случаях, как для поиска, так и для других операций, доступных для отсортированных массивов. Например, поиск приблизительные совпадения и доступные для отсортированных массивов, методы более эффективно, чем двоичный поиск в структурех данных, таких как деревья Ван Эмде Боаса, деревья слияния, пробует и битовые массивы. Эти специализированные структуры обычно работают быстрее, что они используют свойства ключей с определенным атрибутом (обычно используются ключи, которые имеют небольшие целевые числа), и, таким образом, требуют времени или места для ключей без этой атрибута. Пока ключи можно упорядочить, эти операции всегда могут быть обработаны, по крайней мере, эффективно с отсортированным массивом независимо от ключей. Некоторые структуры, такие как массивы Джуди, используют комбинацию подходов для смягчения этого, сохраняя при этой эффективности и приблизительного сопоставления.
Варианты
Унифицированный двоичный поиск
  Унифицированный двоичный поиск изменений между текущими и двумя возможными средними элементами вместо других границ. 
Единый двоичный поиск хранит вместо нижней и верхней границы диапазона в индексе среднего элемента от текущей итерации до следующей итерация. Предварительно вычисленная справочная таблица , содержащая различия. Например, если поиск выполняется в массиве [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], средний элемент ($m\; \{\backslash \; displaystyle\; m\}$) 6. В этом случае средний элемент левого подмассива ([1, 2, 3, 4, 5]) равен 3, средний элемент правого подмассива ([7, 8, 9, 10, 11]) 9. Единый двоичный поиск сохранения значение 3, оба отличаются от 6 на ту же величину. Чтобы уменьшить пространство поиска, алгоритм либо алгоритм либо вычитает это изменение из среднего элемента. Равномерный двоичный поиск может быть быстрее в системах, где неэффективно вычислять среднюю точку, например, на десятичных компьютеровх.
Экспоненциальный поиск
  Визуализация экспоненциального поиска нахождения верхней границы для последующего двоичного поиска 
Экспоненциальный поиск расширяет двоичный поиск до неограниченных списков. Он начинается с поиска первого элемента с индексом, который является степенью двойки и больше целевого значения. После этого он устанавливает этот индекс в качестве верхней границы и переключается на двоичный поиск. Поиск занимает $\lfloor \; log\; 2\; \; x\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; x\; +\; 1\; \backslash \; rfloor\}$итераций до запуска двоичного поиска и не более $\lfloor \; log\; 2\; \; x\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; x\; \backslash \; rfloor\}$итераций двоичного поиска, где $x\; \{\backslash \; textstyle\; x\}$- это положение целевого значения. Экспоненциальный поиск работает с ограниченными списками, но улучшением по сравнению с двоичным поиском становится только в том случае, если целевое значение находится рядом с начальным массивом.
Поиск с интерполяцией
  Предварительный просмотр поиск с интерполяцией с использованием линейного интерполяция. В этом случае поиск не требуется, поскольку оценка местоположения цели в массиве верна. Другие реализации могут указывать функцию для определения местоположения цели. 
Вместо вычисления средней точки поиск с интерполяцией оценивает положение целевого значения, самый высокий во время самого низкого и высокий элементы в массиве, а также длину массива. Он работает на том основании, во многих случаях средняя точка не является лучшим предположением. Например, если целевое значение близко к наивысшему элементу в массиве, оно, вероятно, будет расположено ближе к концу массива.
Распространенная функция интерполяции линейная интерполяция. Если $A\; \{\backslash \; displaystyle\; A\}$- массив, $L,\; R\; \{\backslash \; displaystyle\; L,\; R\}$- нижняя и верхняя границы соответственно и $T\; \{\backslash \; displaystyle\; T\}$- цель, тогда цель оценивается примерно в $(T\; -\; AL)\; /\; (AR\; -\; AL)\; \{\backslash \; displaystyle\; (T-A\_\; \{L\})\; /\; (A\_\; \{R\}\; -A\_\; \{L\})\}$на пути между $L\; \{\backslash \; displaystyle\; L\}$и $R\; \{\backslash \; displaystyle\; R\}$. Когда используется линейная интерполяция и структура элементов равномерно или однородно, поиск с интерполяцией составляет $O\; (log\; \; log\; \; n)\; \{\backslash \; textstyle\; O\; (\backslash \; log\; \backslash \; log\; n)\}$сравнение.
На практике поиска с интерполяцией выполняется медленнее, чем двоичный поиск для небольших массивов, поскольку поиск с интерполяцией требует вычислений. Его временная сложность растет медленнее, чем двоичный поиск, но это только компенсирует дополнительные дополнительные вычисления для больших массивов.
Дробное каскадирование
  В дробном каскадировании каждый массив имеет указатели на каждую секунду элемента другого массива, поэтому для поиска по всем массивам необходимо выполнить только один двоичный поиск. 
Дробное каскадирование - это метод, который ускоряет двоичный поиск одного и того же элемента в нескольких отсортированных массивах. Для поиска в каждом массиве отдельно требуется $O\; (k\; log\; \; n)\; \{\backslash \; textstyle\; O\; (k\; \backslash \; log\; n)\}$время, где $k\; \{\backslash \; textstyle\; k\}$- количество массивов. Дробное каскадирование сокращает это до $O\; (k\; +\; log\; \; n)\; \{\backslash \; textstyle\; O\; (k\; +\; \backslash \; log\; n)\}$, сохраняя в каждом массиве конкретную информацию о каждом элементе и его положении в других массивах..
Дробное каскадирование изначально было разработано для эффективных решений различных вычислительных задач геометрии. Дробное каскадирование применялось повсюду, например, в интеллектуальном анализе данных и маршрутизации по Интернет-протоколу.
Обобщение на графы
Двоичный поиск был обобщен для работы с определенными типами графов, где целевое значение хранится в вершине, а не в элементе массива. Деревья двоичного поиска являются одним из таких обобщений - когда запрашивается вершина (узел) в дереве, алгоритм либо узнает, что вершина конечного цели, либо в противном случае, в каком поддереве будет быть целью. Однако это можно обобщить как следует: для неориентированного положительно взвешенного графа и целевой вершины алгоритм узнает при запросе вершины, что она равна цели, или ему соответствует инцидентное ребро, которое находится на кратчайшем пути от запрашиваемой вершины до цели. Стандартный алгоритм двоичного поиска - это просто случай, когда граф представляет собой путь. Точно так же деревья двоичного поиска - это случай, когда края левого или правого поддеревья задаются, когда запрашиваемая вершина не достигает цели. Для всех неориентированных положительно взвешенных графов существует алгоритм, который находит целевую вершину в $запросах\; O\; (log\; \; n)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; n)\}$в худшем случае.
Шумный двоичный поиск
  При зашумленном двоичном поиске существует определенная вероятность, что сравнение некорректно. 
Шумные алгоритмы двоичного поиска решают случай, когда алгоритм не может надежно сравнивать элементы массива. Для пары элементов существует определенная вероятность того, что алгоритм сделает неправильное сравнение каждой. Шумный двоичный поиск может найти правильное положение цели с заданной вероятностью, которая контролирует надежность полученного местоположения. Каждая зашумленная процедура двоичного поиска должна составлять не менее $(1\; -\; \tau )\; log\; 2\; \; (n)\; H\; (p)\; -\; 10\; H\; (p)\; \{\backslash \; displaystyle\; (1-\; \backslash \; tau)\; \{\backslash \; frac\; \{\backslash \; log\; \_\; \{\; 2\}\; (n)\}\; \{H\; (p)\}\}\; -\; \{\backslash \; frac\; \{10\}\; \{H\; (p)\}\}\}$сравнение в среднем, где $H\; (p)\; =\; -\; p\; log\; 2\; \; (p)\; -\; (1\; -\; p)\; журнал\; 2\; \; (1\; -\; p)\; \{\backslash \; displaystyle\; H\; (p)\; =\; -\; p\; \backslash \; log\; \_\; \{2\}\; (p)\; -\; (1-p)\; \backslash \; log\; \_\; \{2\}\; (1-p)\}$- это двоичная функция энтропии, а $\tau \; \{\backslash \; displaystyle\; \backslash \; tau\}$- вероятность того, что процедура вернет неправильную позицию. Проблема зашумленного двоичного поиска может рассматриваться как случай игры Реньи-Улама, вариант Двадцать вопросов, где ответы могут быть неправильными.
Квантовая двоичная система поиска
Классические компьютеры ограничены до наихудшего случая ровно $\lfloor \; log\; 2\; \; n\; +\; 1\; \rfloor \; \{\backslash \; textstyle\; \backslash \; lfloor\; \backslash \; log\; \_\; \{2\}\; n\; +\; 1\; \backslash \; rfloor\; \}$итераций при выполнении бинарного поиска. Квантовые алгоритмы для двоичного поиска по-прежнему ограничены пропорциями $log\; 2\; \; n\; \{\backslash \; textstyle\; \backslash \; log\; \_\; \{2\}\; n\}$запросов (представляющих итерации классической процедуры), но постоянный коэффициент меньше единицы, что обеспечивает меньшую временную сложность на квантовых компьютеровх. Любая процедура точного квантового двоичного поиска, то есть процедура, которая всегда дает правильный результат, требует как минимум $1\; \pi \; (ln\; \; n\; -\; 1)\; \approx \; 0,22\; log\; 2\; \; n\; \{\backslash \; textstyle\; \{\backslash \; frac\; \{1\}\; \{\; \backslash \; pi\}\}\; (\backslash \; ln\; n-1)\; \backslash \; приблизительно\; 0,22\; \backslash \; log\; \_\; \{2\}\; n\}$запросов в худшем случае, где $ln\; \{\backslash \; textstyle\; \backslash \; ln\}$- натуральный логарифм. Существует точная процедура квантового двоичного поиска, которая выполняется в $4\; log\; 605\; \; n\; \approx \; 0,433\; log\; 2\; \; n\; \{\backslash \; textstyle\; 4\; \backslash \; log\; \_\; \{605\}\; n\; \backslash \; приблизительно\; 0,433\; \backslash \; log\; \_\; \{2\}\; n\}$запросов в худшем случае. Для сравнения: алгоритм Гровера является оптимальным квантовым алгоритмом для поиска неупорядоченного списка элементов, и для него требуется $O\; (n)\; \{\backslash \; displaystyle\; O\; (\{\backslash \; sqrt\; \{n\}\})\}$запросов.
История
Идея сортировки списка элементов для ускорения поиска восходит к древности. Самым ранним известным примером была табличка Инакибит-Ану из Вавилона, датируемая ок. 200 г. до н. Э. Табличка содержала около 500 шестидесятеричных чисел и их обратных, отсортированных в лексикографическом порядке, что упростило поиск конкретной записи. Кроме того, на Эгейских островах было обнаружено несколько списков имен, отсортированных по первой букве. Католикон, латинский словарь, законченный в 1286 году н.э., был первой работой, описывающей правила сортировки слов в алфавитном порядке, а не только по первым буквам.
В 1946 году Джон Мочли впервые представнул о двоичном поиске в рамках лекций школы Мура, основополагающего и основополагающего курса колледжа по информатике. В 1957 году Уильям Уэсли Петерсон опубликовал первый метод интерполяционного поиска. Каждый опубликованный алгоритм поиска работал только с алгоритмами, длина которых на единицу меньше степени двойки, до 1960 года, когда Деррик Генри Лемер опубликовал алгоритм работы одного двоичного поиска, который работал со всеми массивами. В 1962 году Герман Боттенбрух представил выполнение бинарного поиска ALGOL 60, которое в сравнении на равенство помещается в конец, увеличивая среднее количество итераций на единицу, но уменьшая до числа единицы. сравнений на итерацию. унифицированный двоичный поиск был разработан А.К. Чандра из Стэнфордского университета в 1971 году. В 1986 году Бернард Чазел и Леонидас Дж. Гибас представили дробное каскадирование как методы решения задач проблем поиска в вычислительной геометрии.
Проблемы реализации
Хотя основная идея двоичного поиска относительно проста, могут быть на удивление сложными
— Дональд Кнут 
Когда Джон Бентли назначил двоичный поиск проблемы в профессиональных программистов, он обнаружил, что девяносто процентов не смогло предоставить правильное решение после нескольких часов работы над ним. запустить или вернули неправильный ответ в редких пограничных случаев. Исследование опубликованное в 1988 году, показывает, что точный код для него можно найти только в пяти из двадцати учебников. Более того, реализация двоичного поиска Бентли, опубликованная в его книге «Жемчужины программирования» 1986 года, содержала ошибку переполнения , которая оставалась незамеченной более двадцати лет. Реализация двоичного поиска в библиотеке языка программирования Java имеет ту же ошибку переполнения более девяти лет.
На практике переменные, используемые для представексов, будут иметь фиксированный размер, и это может привести к арифметическому переполнению  для очень больших массивов. Если средняя точка диапазона вычисляется как $L\; +\; R\; 2\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{L\; +\; R\}\; \{2\}\}\}$, то значение $L\; +\; R\; \{\backslash \; displaystyle\; L\; +\; R\; \}$может быть диапазон целых чисел типа данных, используемого для хранения средней точки, даже если $L\; \{\backslash \; displaystyle\; L\}$и $R\; \{\backslash \; displaystyle\; R\}$находятся в пределах диапазона. Если $L\; \{\backslash \; displaystyle\; L\}$и $R\; \{\backslash \; displaystyle\; R\}$рицательны, этого можно избежать, вычислив среднюю точку как $L\; +\; R\; -\; L\; 2\; \{\backslash \; displaystyle\; L\; +\; \{\backslash \; frac\; \{RL\}\; \{2\}\}\}$.
Бесконечный цикл может возникнуть, если условия выхода для не найденного цикла правильно. Как только $L\; \{\backslash \; displaystyle\; L\}$больше $R\; \{\backslash \; displaystyle\; R\}$, поиск завершился неудачно и должен сообщить об ошибке поиска. Кроме того, цикл должен быть завершен, когда элемент найден, или в случае реализации, где эта проверка перемещена в конце, был ли поиск успешным или неудачным в конце. Bentley обнаружил, что большинство программистов, которые реализовали двоичный поиск, сделали ошибку при определении условий выхода.
Поддержка библиотек
Стандартные библиотеки многих языков включают подпрограммы двоичного поиска:
C предоставляет функцию  bsearch ()в своей стандартной библиотеке, которая обычно реализуется посредством двоичного поиска, хотя официальный стандарт не требует этого, поэтому.
Стандартная библиотека шаблонов C ++  предоставляет функции binary_search (), lower_bound (), upper_bound ()и equal_range ().
D в стандартной библиотеке Phobos в модуле std.rangeпредоставляет тип SortedRange(возвращается функция sort ()и acceptSorted ()functions) с методами contains (), equaleRange (), lowerBound ()и trisect (), которые по умолчанию используйте методы двоичного поиска для диапазонов с произвольным доступом.
COBOL обеспечивает SEAR Команда CH ALLдля выполнения двоичного поиска в упорядоченных таблицах COBOL. Стандартный пакет библиотеки sort
Go содержит функции Search, SearchInts, SearchFloat64sи SearchStrings, которые реализуют общие двоичный поиск, а также реализация для поиска срезов целых чисел, чисел с плавающей запятой и соответственно строк.
Java предлагает набор перегруженных статических методов binarySearch ()в классах Arrays и Collections в стандартном пакете java.utilдля выполнения двоичного поиска в массивах Java и в Listсоответственно.
Microsoft .NET Framework 2.0 предлагает статические общие версии алгоритма двоичного поиска в своих базовых классах коллекции. Примером может быть метод System.ArrayBinarySearch (массив T, значение T).
Для Objective-C, Какао framework. метод NSArray -indexOfObject: inSortedRange: options: usingComparator: в Mac OS X 10.6+. Структура Apple Core Foundation C также обеспечивает функцию CFArrayBSearchValues() .
Python предоставляет модуль пополам.
Класс Array Ruby включает метод bsearchсо встроенным приближенным сопоставлением.
См. Также
Метод деления пополам - Алгоритм для поиска нуля функции - та же идея, использовалась для решения чисел в вещественных числах
Мультипликативный двоичный поиск - Вариант двоичного поиска с упрощенным вычислением средней точки
Примечания и ссылки
 Эта статья была отправлена ​​в WikiJournal of Science для внешней академическая экспертная оценка в 2018 г. (отчеты рецензентов ). Обновленный контент был повторно интегрирован на страницу Википедии под лицензией CC-BY-SA-3.0 (). Пересмотренная версия записи: Энтони Лин; и другие. (2019), «Алгоритм двоичного поиска», WikiJournal of Science, 2 (1): 5, doi : 10.15347 / WJS / 2019.005, Wikidata Q81434400 
Примечания
Цитаты
Работы
Бентли, Джон (2000). Жемчужины программирования (2-е изд.). Эддисон-Уэсли. ISBN 978-0-201-65788-3. CS1 maint: ref = harv (ссылка )
Баттерфилд, Эндрю; Нгонди, Джерард Э. (2016). Словарь информатики (7-е изд.). Оксфорд, Великобритания: Oxford University Press. ISBN 978-0-19-968897-5. CS1 maint: ref = harv (ссылка )
Чанг, Ши-Куо ( 2003). Структуры данных и алгоритмы. Программная инженерия и разработка знаний. 13 . Сингапур: World Scientific. ISBN 978-981-238-348 -8. CS1 maint: ref = harv (ссылка )
Cormen, Thomas X. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 978-0-262-03384-8. CS1 maint: ref = harv (ссылка )
Фитцджеральд, Майкл (2015). Справочник по карману Ruby. Севастополь, Калифорния: O'Reilly Media. ISBN 978-1-4919-2601-7. CS1 maint: ref = harv (ссылка )
Перейти Лдман, Салли А.; Голдман, Кеннет Дж. (2008). Практическое руководство по структурем данных и алгоритмам с использованием Java. Бока-Ратон, Флорида: CRC Press. ISBN 978-1-58488-455-2. CS1 maint: ref = harv (ссылка )
Касахара, Масахиро; Моришита, Шиничи (2006). Крупномасштабная обработка следовать генома. Лондон, Великобритания: Imperial College Press. ISBN 978-1-86094-635-6. CS1 maint: ref = harv (ссылка )
Кнут, Дональд (1997). Фундаментальные алгоритмы. Искусство компьютерного программирования. 1(3-е изд.). Чтение, Массачусетс: Addison-Wesley Professional. ISBN 978-0-201-89683-1. CS1 maint: ref = harv (link )
Knuth, Donald (1998). Сортировка и поиск. Искусство компьютерного программирования. 3(2-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN 978-0-201-89685-5. CS1 maint: ref = harv (ссылка )
Кнут, Дональд (2011). Комбинаторные алгоритмы. Искусство компьютерного программирования. 4A(1-е изд.). Чтение, Массачусетс: Addison -Wesley Professional. ISBN 978-0-201-03804-0. CS1 maint: ref = harv (ссылка )
Моффат, Алистер; Турпин, Андрей (2002). Алгоритмы сжатия и кодирования. Гамбург, Германия: Kluwer Academic Publishers. DOI : 10.1007 / 978-1-4615-0935-6. ISBN 978-0-7923-7668-2. CS1 maint: ref = harv (ссылка )
Седжвик, Роберт ; Уэйн, Кевин (2011). Алгоритмы (4-е изд.). Аппер Сэддл Ривер, Нью-Джерси: Addison-Wesley Professional. ISBN 978-0-321-57351-3. CS1 maint: ref = harv (ссылка ) Сжатая веб-версия  ; версия книги .
Страуструп, Бьярне (2013 г.). Язык программирования C ++ ( 4-е изд.). Аппер-Сэдл-Ривер, Нью-Джерси: Addison-Wesley Professional. ISBN 978-0-321-56384-2. CS1 maint: ref = harv ( ссылка )
Внешние ссылки
Викибук Реализация алгоритма имеет страницу по теме: Двоичный поиск 
Словарь алгоритмов и структур данных NIST: двоичный search 
Сравнения и тесты различных реализаций двоичного поиска в C