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

В Информатика, экспоненциальный поиск (также называемый двойной поиск или же скачущий поиск или же Струзик поиск)^[1] является алгоритм, сделано Джон Бентли и Эндрю Чи-Чи Яо в 1976 г. для поиска в отсортированных неограниченных / бесконечных списках.^[2] Существует множество способов реализовать это, наиболее распространенным из которых является определение диапазона, в котором находится ключ поиска, и выполнение бинарный поиск в этом диапазоне. Это требует О (бревноя) куда я - это позиция ключа поиска в списке, если ключ поиска находится в списке, или позиция, где должен быть ключ поиска, если ключа поиска нет в списке.

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

Алгоритм

Экспоненциальный поиск позволяет выполнять поиск в отсортированном неограниченном списке по заданному входному значению («ключ» поиска). Алгоритм состоит из двух этапов. На первом этапе определяется диапазон, в котором находился бы ключ поиска, если бы он был в списке. На втором этапе по этому диапазону выполняется двоичный поиск. На первом этапе, предполагая, что список отсортирован в порядке возрастания, алгоритм ищет первый показатель степени, j, где значение 2^j больше ключа поиска. Это значение, 2^j становится верхней границей для двоичного поиска с предыдущей степенью 2, 2^{j - 1}, являющаяся нижней границей двоичного поиска.^[3]

// Возвращает позицию ключа в массиве arr длины size.шаблон <typename Т>int exponential_search(Т обр[], int размер, Т ключ){    если (размер == 0) {        возвращаться НЕ НАЙДЕН;    }    int граница = 1;    пока (граница < размер && обр[граница] < ключ) {        граница *= 2;    }    возвращаться binary_search(обр, ключ, граница/2, мин(граница + 1, размер));}

На каждом этапе алгоритм сравнивает значение ключа поиска со значением ключа в текущем индексе поиска. Если элемент в текущем индексе меньше, чем ключ поиска, алгоритм повторяется, переходя к следующему индексу поиска, удваивая его, вычисляя следующую степень двойки.^[3] Если элемент в текущем индексе больше, чем ключ поиска, алгоритм теперь знает, что ключ поиска, если он вообще содержится в списке, находится в интервале, образованном предыдущим индексом поиска, 2^{j - 1}, и текущий поисковый индекс, 2^j. Затем выполняется двоичный поиск с результатом либо сбоя, если ключ поиска отсутствует в списке, либо положения ключа поиска в списке.

Спектакль

Первый этап алгоритма занимает О(бревноя) время, где я - это индекс, по которому в списке будет находиться ключ поиска. Это связано с тем, что при определении верхней границы для двоичного поиска цикл while выполняется точно ${ Displaystyle lceil журнал (я) rceil}$ раз. Поскольку список отсортирован, после удвоения поискового индекса ${ Displaystyle lceil журнал (я) rceil}$ раз алгоритм будет в поисковом индексе, который больше или равен я в качестве ${ Displaystyle 2 ^ { lceil log (я) rceil} geq я}$. Таким образом, первый этап алгоритма занимает О(бревноя) время.

Вторая часть алгоритма также занимает О(бревноя) время. Поскольку второй этап - это просто двоичный поиск, требуется О(бревноп) куда п размер искомого интервала. Размер этого интервала будет 2^j - 2^{j - 1} где, как видно выше, j = журналя. Это означает, что размер искомого интервала равен 2.^{бревно я} - 2^{бревно я - 1} = 2^{бревно я - 1}. Это дает нам время выполнения журнала (2^{бревно я - 1}) = журнал (я) - 1 = О(бревноя).

Это дает алгоритму общее время выполнения, рассчитанное путем суммирования времени выполнения двух этапов О(бревноя) + О(бревноя) = 2 О(бревноя) = О(бревноя).

Альтернативы

Бентли и Яо предложили несколько вариантов экспоненциального поиска.^[2] Эти варианты состоят в выполнении двоичного поиска, в отличие от унарного поиска, при определении верхней границы двоичного поиска на втором этапе алгоритма. Это разбивает первый этап алгоритма на две части, что делает алгоритм в целом трехэтапным. Новый первый этап определяет значение ${ displaystyle j '}$, как и раньше, так что ${ displaystyle 2 ^ {j '}}$ больше ключа поиска и ${ displaystyle 2 ^ {j '/ 2}}$ ниже ключа поиска. Ранее, ${ displaystyle j '}$ был определен унарным способом путем вычисления следующей степени двойки (т. е. прибавления 1 к j). В варианте предлагается, чтобы ${ displaystyle j '}$ вместо этого удваивается (например, прыжок с 2² до 2⁴ в отличие от 2³). Первый ${ displaystyle j '}$ такой, что ${ displaystyle 2 ^ {j '}}$ больше, чем ключ поиска, образует гораздо более грубую верхнюю границу, чем раньше. Однажды это ${ displaystyle j '}$ найден, алгоритм переходит ко второму этапу, и выполняется двоичный поиск на интервале, образованном ${ displaystyle j '/ 2}$ и ${ displaystyle j '}$, что дает более точный показатель степени верхней границы j. Отсюда третий этап алгоритма выполняет двоичный поиск на интервале 2^{j - 1} и 2^j, как прежде. Производительность этого варианта ${ Displaystyle lfloor log i rfloor +2 lfloor log ( lfloor log i rfloor +1) rfloor +1}$ = О(бревноя).

Бентли и Яо обобщают этот вариант в одном, где любое число, k, бинарных поисков выполняются на первом этапе алгоритма, что дает k-вложенный вариант двоичного поиска. Асимптотическое время выполнения не меняется для вариантов, работающих в О(бревноя) времени, как и в исходном алгоритме экспоненциального поиска.

Кроме того, структура данных с плотной версией динамическое свойство пальца может быть дан, когда приведенный выше результат k-вложенный двоичный поиск используется в отсортированном массиве.^[4] Используя это, количество сравнений, сделанных во время поиска, составляет log (d) + журнал журнал (d) + ... + О(бревно^*d), куда d это разница в ранге между последним элементом, к которому был осуществлен доступ, и текущим элементом, к которому был осуществлен доступ.

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

• Линейный поиск
• Бинарный поиск
• Поиск интерполяции
• Тернарный поиск
• Хеш-таблица

Рекомендации