Algorithm
Exponential search allows for searching through a sorted, unbounded list for a specified input value (the search "key"). The algorithm consists of two stages. 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 2 is greater than the search key. This value, 2 becomes the upper bound for the binary search with the previous power of 2, 2, being the lower bound for the binary search.Performance
The first stage of the algorithm takes ''O''(log ''i'') time, where ''i'' 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 times. 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 such, the first stage of the algorithm takes ''O''(log ''i'') time. The second part of the algorithm also takes ''O''(log ''i'') time. As the second stage is simply a binary search, it takes ''O''(log ''n'') where ''n'' is the size of the interval being searched. The size of this interval would be 2 - 2 where, as seen above, ''j'' = log ''i''. This means that the size of the interval being searched is 2 - 2 = 2. This gives us a run time of log (2) = log (''i'') - 1 = ''O''(log ''i''). This gives the algorithm a total runtime, calculated by summing the runtimes of the two stages, of ''O''(log ''i'') + ''O''(log ''i'') = 2 ''O''(log ''i'') = ''O''(log ''i'').Alternatives
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 '''', much like before, such that is larger than the search key and is lower than the search key. Previously, '''' 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 is doubled instead (e.g., jumping from 2 to 2 as opposed to 2). The first '''' such that is greater than the search key forms a much rougher upper bound than before. Once this '''' is found, the algorithm moves to its second stage and a binary search is performed on the interval formed by and , giving the more accurate upper bound exponent ''j''. From here, the third stage of the algorithm performs the binary search on the interval 2 and 2, as before. The performance of this variation is = ''O''(log ''i''). 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 ''O''(log ''i'') 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. Using this, the number of comparisons done during a search is log (''d'') + log log (''d'') + ... + ''O''(log ''d''), where ''d'' is the difference in rank between the last element that was accessed and the current element being accessed.See also
* Linear search *References
{{Reflist, refs= {{citation, contribution=Fast intersection algorithms for sorted sequences, first1=Ricardo, last1=Baeza-Yates, author1-link= Ricardo Baeza-Yates , first2=Alejandro, last2=Salinger, title=Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday, volume=6060, series=Lecture Notes in Computer Science, editor1-first=Tapio, editor1-last=Elomaa, editor2-first=Heikki, editor2-last=Mannila, editor2-link=Heikki Mannila, editor3-first=Pekka, editor3-last=Orponen, publisher=Springer, year=2010, isbn=9783642124754, pages=45–61, doi=10.1007/978-3-642-12476-1_3, bibcode=2010LNCS.6060...45B. {{cite journal , last1 = Bentley , first1 = Jon L. , author1-link = Jon Bentley (computer scientist) , last2 = Yao , first2 = Andrew C. , author2-link = Andrew Yao , title = An almost optimal algorithm for unbounded searching , year = 1976 , journal = Information Processing Letters , volume = 5 , issue = 3 , pages = 82–87 , issn = 0020-0190 , doi = 10.1016/0020-0190(76)90071-5 {{cite web , url = https://sites.google.com/site/d7013e11/announcements/exponentialbinarysearch , accessdate = 2014-03-24 , title = Exponential Binary Search , first = Håkan , last = Jonsson , date = 2011-04-19 {{cite journal , last1 = Andersson , first1 = Arne , last2 = Thorup , first2 = Mikkel , author2-link = Mikkel Thorup , title = Dynamic ordered sets with exponential search trees , year = 2007 , journal =