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

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

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

В информатике , двоичный поиск , также известная как полуинтервал поиск , ^[1] логарифмическая поиска , ^[2] или двоичные отбивной , ^[3] является алгоритмом поиска , который находит позицию целевого значения в пределах отсортированного массива . ^{[4] [5]}Двоичный поиск сравнивает целевое значение со средним элементом массива. Если они не равны, половина, в которой не может находиться цель, удаляется, и поиск продолжается на оставшейся половине, снова беря средний элемент для сравнения с целевым значением и повторяя это до тех пор, пока целевое значение не будет найдено. Если поиск заканчивается тем, что оставшаяся половина оказывается пустой, цель отсутствует в массиве.

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

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

Алгоритм [ править ]

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

Процедура [ править ]

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

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

Эта итерационная процедура отслеживает границы поиска с помощью двух переменных и . Процедура может быть выражена в псевдокоде следующим образом, где имена и типы переменных остаются такими же, как указано выше, является функцией пола и относится к определенному значению, которое сообщает об ошибке поиска. ^[7]${\ displaystyle L}$${\ displaystyle R}$floorunsuccessful

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

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

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

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

Герман Боттенбрух опубликовал первую реализацию без этой проверки в 1962 году. ^{[8] [9]}

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

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

функция binary_search_alternative (A, n, T) является L: = 0 R: = n - 1 а L! = R делаем m: = ceil ((L + R) / 2) если A [m]> T, то R: = м - 1 еще : L: = м если A [L] = T, то  вернуть L вернуть неудачно

Повторяющиеся элементы [ править ]

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

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

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

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

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

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

функция binary_search_leftmost (A, n, T): L: = 0 R: = n пока L <R: м: = этаж ((L + R) / 2) если A [m] <T: L: = m + 1 еще : R: = м вернуть L

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

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

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

Если и , то это самый правый элемент, который равен . Даже если нет в массиве, количество элементов в массиве больше, чем .${\ displaystyle L> 0}$${\ displaystyle A_ {R-1} = T}$${\ displaystyle A_ {R-1}}$${\ displaystyle T}$${\ displaystyle T}$${\ Displaystyle п-R + 1}$${\ displaystyle T}$

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

функция binary_search_rightmost (A, n, T): L: = 0 R: = n пока L <R: м: = этаж ((L + R) / 2) если A [m]> T: R: = м еще : L: = m + 1 возврат R - 1

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

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

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

• Ранговые запросы могут выполняться с помощью процедуры поиска крайнего левого элемента . Число элементов меньше целевого значения возвращается процедурой. ^[11]
• Запросы-предшественники могут выполняться с запросами ранжирования. Если ранг целевого значения равен , то его предшественник  . ^[12]${\ displaystyle r}$${\ displaystyle r-1}$
• Для запросов-преемников может использоваться процедура поиска самого правого элемента . Если результат выполнения процедуры для целевого значения равен , то преемником целевого значения является  . ^[12]${\ displaystyle r}$${\ displaystyle r + 1}$
• Ближайшим соседом целевого значения является его предшественник или последователь, в зависимости от того, что ближе.
• Запросы диапазона также просты. ^[12] Как только ранги двух значений известны, количество элементов, больше или равных первому значению и меньше второго, является разницей между двумя рангами. Этот счетчик может быть увеличен или уменьшен на единицу в зависимости от того, следует ли считать конечные точки диапазона частью диапазона и содержит ли массив записи, соответствующие этим конечным точкам. ^[13]

Производительность [ править ]

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

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

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

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

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

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

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

Космическая сложность [ править ]

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

Вывод среднего случая [ править ]

Среднее количество итераций, выполняемых двоичным поиском, зависит от вероятности поиска каждого элемента. Средний случай отличается для успешных поисков и неудачных поисков. Предполагается, что каждый элемент с одинаковой вероятностью будет подвергнут успешному поиску. Для безуспешных поисков предполагается, что интервалы между и внешними элементами будут искать с одинаковой вероятностью. Средний случай успешного поиска - это количество итераций, необходимых для поиска каждого элемента ровно один раз, деленное на количество элементов. Средний случай неудачных поисков - это количество итераций, необходимых для поиска элемента в каждом интервале ровно один раз, деленное на интервалы. ^[14]${\displaystyle n}$${\displaystyle n+1}$

Успешные поиски [ править ]

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

Поскольку двоичный поиск является оптимальным алгоритмом поиска со сравнениями, эта проблема сводится к вычислению минимальной длины внутреннего пути всех двоичных деревьев с узлами, которая равна: ^[17]${\displaystyle n}$

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

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

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

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

${\displaystyle 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}$

Подставляя уравнение для в уравнение для : ^[14]${\displaystyle I(n)}$${\displaystyle T(n)}$

${\displaystyle 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}$

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

Неудачные поиски [ править ]

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

Подобным образом эту задачу можно свести к определению минимальной длины внешнего пути всех двоичных деревьев с узлами. Для всех двоичных деревьев длина внешнего пути равна длине внутреннего пути плюс . ^[17] Подставляя уравнение для : ^[14]${\displaystyle n}$${\displaystyle 2n}$${\displaystyle I(n)}$

${\displaystyle 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}}$

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

${\displaystyle 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}$. ^{[c] [18] [19]}

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

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

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

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

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

Линейный поиск [ править ]

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

Деревья [ править ]

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

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

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

Хеширование [ править ]

Для реализации ассоциативных массивов , хэш - таблицы , структура данных , которая отображает ключи записей с использованием хеш - функции , как правило , быстрее , чем бинарный поиск в отсортированном массиве записей. ^{[32] Для} большинства реализаций хэш-таблиц в среднем требуется только амортизированное постоянное время. ^{[f] [34]} Однако хеширование бесполезно для приблизительных совпадений, таких как вычисление следующего наименьшего, следующего наибольшего и ближайшего ключей, поскольку единственная информация, предоставляемая при неудачном поиске, - это то, что цель отсутствует ни в одном записывать. ^[35]Для таких совпадений идеально подходит двоичный поиск, выполняющий их за логарифмическое время. Двоичный поиск также поддерживает приблизительные совпадения. Некоторые операции, такие как поиск наименьшего и наибольшего элемента, можно эффективно выполнять с отсортированными массивами, но не с хеш-таблицами. ^[22]

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

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

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

Другие структуры данных [ править ]

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

Варианты [ править ]

Единый двоичный поиск [ править ]

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

Экспоненциальный поиск[ редактировать ]

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

Поиск с интерполяцией [ править ]

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

Обычной функцией интерполяции является линейная интерполяция . Если - массив, - нижняя и верхняя границы соответственно, и - цель, то цель оценивается как примерно посередине между и . Когда используется линейная интерполяция и распределение элементов массива равномерное или почти равномерное, поиск с интерполяцией выполняет сравнения. ^{[43] [44] [45]}${\displaystyle A}$${\displaystyle L,R}$${\displaystyle T}$${\displaystyle (T-A_{L})/(A_{R}-A_{L})}$${\displaystyle L}$${\displaystyle R}$${\textstyle O(\log \log n)}$

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

Дробное каскадирование [ править ]

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

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

Обобщение на графики [ править ]

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

Шумный двоичный поиск [ править ]

Шумные алгоритмы двоичного поиска решают случай, когда алгоритм не может надежно сравнивать элементы массива. Для каждой пары элементов существует определенная вероятность того, что алгоритм сделает неправильное сравнение. Шумный двоичный поиск может найти правильное положение цели с заданной вероятностью, которая контролирует надежность полученного местоположения. Каждая зашумленная процедура двоичного поиска должна производить по крайней мере сравнения в среднем, где - двоичная функция энтропии и - вероятность того, что процедура дает неправильную позицию. ^{[49] [50] [51]} Проблема зашумленного двоичного поиска может рассматриваться как случай игры Реньи-Улама , ^[52] вариант${\displaystyle (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}}$${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$${\displaystyle \tau }$Двадцать вопросов, ответы на которые могут быть неправильными. ^[53]

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

Классические компьютеры ограничиваются наихудшим случаем ровно итераций при выполнении двоичного поиска. Квантовые алгоритмы двоичного поиска по-прежнему ограничены определенной долей запросов (представляющих итерации классической процедуры), но постоянный коэффициент меньше единицы, что обеспечивает меньшую временную сложность на квантовых компьютерах . Любая процедура точного квантового двоичного поиска, то есть процедура, которая всегда дает правильный результат, требует как минимум запросов в худшем случае, где - натуральный логарифм . ^[54] Существует точная процедура квантового двоичного поиска, которая выполняется в запросах в худшем случае. ^[55]${\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}$Для сравнения : алгоритм Гровера является оптимальным квантовым алгоритмом для поиска неупорядоченного списка элементов и требует запросов. ^[56]${\displaystyle O({\sqrt {n}})}$

История [ править ]

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

В 1946 году Джон Мочли впервые упомянул о двоичном поиске в рамках лекций школы Мура , основополагающего и основополагающего курса колледжа по информатике. ^[9] В 1957 году Уильям Уэсли Петерсон опубликовал первый метод интерполяционного поиска. ^{[9] [57]} Каждый опубликованный алгоритм двоичного поиска работал только с массивами, длина которых на единицу меньше степени двойки ^[i] до 1960 года, когда Деррик Генри Лемер опубликовал алгоритм двоичного поиска, который работал со всеми массивами. ^[59] В 1962 году Герман Боттенбрух представил реализацию двоичного поиска на Алголе 60 , в которойсравнение на равенство в конце , увеличивая среднее количество итераций на одну, но уменьшая до одного количество сравнений на итерацию. ^[8] равномерный бинарный поиск был разработан АК Chandra из Стэнфордского университета в 1971 г. ^[9] В 1986 годе Бернард Чазел и Леонидас J Гибас введены дробного каскадирования в качестве способа решения многочисленных проблем поиска в вычислительной геометрии . ^{[46] [60] [61]}

Проблемы реализации [ править ]

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

-  Дональд Кнут ^[2]

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

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

Бесконечный цикл может возникнуть, если условия выхода для цикла определены неправильно. После превышения поиск не удался и должен указывать на неудачу поиска. Кроме того, цикл должен быть завершен, когда целевой элемент найден, или в случае реализации, в которой эта проверка перемещена в конец, должна быть на месте проверка того, был ли поиск успешным или неудачным. Бентли обнаружил, что большинство программистов, которые неправильно реализовали двоичный поиск, делали ошибку при определении условий выхода. ^{[8] [66]}${\displaystyle L}$${\displaystyle R}$

Поддержка библиотеки [ править ]

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

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

См. Также [ править ]

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

Примечания и ссылки [ править ]

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

Заметки [ править ]

Цитаты [ править ]

Источники [ править ]

Внешние ссылки [ править ]

В реализации алгоритма Викибука есть страница по теме: Двоичный поиск

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