In computer science, an exponential search (also called doubling search or galloping search or Struzik search)[1] is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists.
[2] There are numerous ways to implement this, with the most common being to determine a range that the search key resides in and performing a binary search within that range.
is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list.
The first stage determines a range in which the search key would reside if it were in the list.
In the second stage, a binary search is performed on this range.
In the first stage, assuming that the list is sorted in ascending order, the algorithm looks for the first exponent, j, where the value 2j is greater than the search key.
This value, 2j becomes the upper bound for the binary search with the previous power of 2, 2j - 1, being the lower bound for the binary search.
[3] 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.
[3] 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, 2j - 1, and the current search index, 2j.
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.
is the index where the search key would be in the list.
This is because, in determining the upper bound for the binary search, the while loop is executed exactly
Since the list is sorted, after doubling the search index
times, the algorithm will be at a search index that is greater than or equal to i as
As the second stage is simply a binary search, it takes
This means that the size of the interval being searched is 2log i - 2log i - 1 = 2log i - 1.
This gives the algorithm a total runtime, calculated by summing the runtimes of the two stages, of
Bentley and Yao suggested several variations for exponential search.
[2] 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.
was determined in a unary fashion by calculating the next power of 2 (i.e., adding 1 to j).
is greater than the search key forms a much rougher upper bound than before.
is found, the algorithm moves to its second stage and a binary search is performed on the interval formed by
, giving the more accurate upper bound exponent j.
From here, the third stage of the algorithm performs the binary search on the interval 2j - 1 and 2j, as before.
Bentley and Yao generalize this variation into one where any number, k, of binary searches are performed during the first stage of the algorithm, giving the k-nested binary search variation.
The asymptotic runtime does not change for the variations, running in
time, as with the original exponential search algorithm.
Also, a data structure with a tight version of the dynamic finger property can be given when the above result of the k-nested binary search is used on a sorted array.
An algorithm based on exponentially increasing the search band solves global pairwise alignment for