Экспоненциальный поиск был разработан Джоном Бентли и Эндрю Чи-Чи Яо в ​​1976 году для поиска в отсортированных неограничных/бесконечных списках. Существует много способов, чтобы реализовать экспоненциальный поиск, но наиболее распространненый способ заключается в том, чтобы определить диапазон в котором находится ключ. после нахождения нужного диапазона, запскается бинарный поиск на диапазоне. Это занимает O(log i), где i - позиция искомого ключа в списке если он находится в нем, либо позиция в списке на котором он бы стоял если бы присутсвовал.

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

Описание алгоритма

Каким образом мы можем найти диапазон в котором находится искомый элемент?

Идея состоит в том, чтобы начать с подмассива размера 1 сравнить его последний элемент с искомым $$x$$, затем удвоить размер подмассива и опять сравнить и так далее до тех пор, пока последний элемент подмассива не будет больше искомого. Как только мы найдем индекс i (после повторного удвоения i), мы знаем, что элемент должен находиться между i / 2 и i. Затем запускаем бинарный поиск на данном подмассиве и находим элемент.

Таким образом алгоритм экспоненциального поиска состоит из двух шагов:

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

Визуализация работы алгоритма

Реализация алгоритма

int exponentialSearch(int arr[], int n, int x)
{
    // If x is present at firt location itself
    if (arr[0] == x)
        return 0;

    // Find range for binary search by
    // repeated doubling
    int i = 1;
    while (i < n && arr[i] <= x)
        i = i*2;

    //  Call binary search for the found range.
    return binarySearch(arr, i/2, min(i, n), x);
}

In each step, the algorithm compares the search key value with the key value at the current search index. If the element at the current index is smaller than the search key, the algorithm repeats, skipping to the next search index by doubling it, calculating the next power of 2. If the element at the current index is larger than the search key, the algorithm now knows that the search key, if it is contained in the list at all, is located in the interval formed by the previous search index, 2^{j - 1}, and the current search index, 2^j. The binary search is then performed with the result of either a failure, if the search key is not in the list, or the position of the search key in the list.

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

Первый этап алгоритма занимает $$\mathcal{O}(\log i)$$ времени, где $$i$$ - позиция искомого элемента в списке (либо позиция на которой он должен стоят, в случае его отсутсвия). Так происходит, потому что при определении верхней границы подмассива в котором будет отрабатывать бинарный поиск, цикл while будет отрабабатывать ровно $$2^{[\log i]}$$ раз. поскольку массив отсортирован, после удвоения индекса $$[\log i]$$ раз, алгоритм найдет индекс который больше либо равен чем $$i$$ поскольку $$2^{[\log i]} \geq i$$. Таким образом первый этап алгоритма занимает $$\mathcal{O}(\log i)$$ времени.

Второй этап алгоритма так же занимает $$\mathcal{O}(\log i)$$ времени. Поскольку второй шаг это всего лишь бинарный поиск, а его сложность равна $$\mathcal{O}(n)$$, где $$n$$ - количество элементов в интервале поиска. Размер интервала на котором осуществляется поиск равен $$2^j-2^{j-1}$$ где $$j = \log i$$. Таким образом размер интервала равен $$2^{\log i} - 2^{\log i - 1} = 2^{\log i - 1}$$ Таким образом на бианрный поиск потребуется $$\mathcal{O}(\log n) = \mathcal{O}(\log (2^{\log i - 1})) = \mathcal{O}(\log i)$$.

Итак, суммируя оба этапа алгоритма, получаем финальную сложность $$\mathcal{O}(\log i) + \mathcal{O}(\log i) = 2\mathcal{O}(\log i) = \mathcal{O}(\log i)$$

Оптимизации

Bentley and Yao suggested several variations for exponential search. These variations consist of performing a binary search, as opposed to a unary search, when determining the upper bound for the binary search in the second stage of the algorithm. This splits the first stage of the algorithm into two parts, making the algorithm a three-stage algorithm overall. The new first stage determines a value $${\displaystyle j'}$$, much like before, such that $${\displaystyle 2^{j'}}$$ is larger than the search key and $${\displaystyle 2^{j'/2}}$$ is lower than the search key. Previously, $${\displaystyle j'}$$ was determined in a unary fashion by calculating the next power of 2 (i.e., adding 1 to j). In the variation, it is proposed that $${\displaystyle j'}$$ is doubled instead (e.g., jumping from $$2^2$$ to $$2^4$$ as opposed to $$2^3$$). The first $${\displaystyle j'}$$ such that $${\displaystyle 2^{j'}}$$ is greater than the search key forms a much rougher upper bound than before. Once this $${\displaystyle j'}$$ is found, the algorithm moves to its second stage and a binary search is performed on the interval formed by $${\displaystyle j'/2}$$ and $${\displaystyle j'}$$, giving the more accurate upper bound exponent j. From here, the third stage of the algorithm performs the binary search on the interval $$2^{j- 1}$$ and $$2^j$$, as before. The performance of this variation is $${\displaystyle \lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1}=O(\log i)$$.

Bentley and Yao generalize this variation into one where any number,k, of binary searches is performed during the first stage of the algorithm, giving thek-nested binary search variation. The asymptotic runtime does not change for the variations, running in O(log i) time, as with the original exponential search algorithm.

Характеристики алгоритма

Приложение и задачи решаемые с помощью экспоненциального поиска

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

Источники информации и полезные ссылки

http://www.geeksforgeeks.org/exponential-search/

http://www.geeksforgeeks.org/find-the-point-where-a-function-becomes-negative/

http://algorithmsgeek.blogspot.ru/2013/06/algo26-binary-search-in-unbounded-array.html