Exponential search
In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. 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. This takes O(log i) where i 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.
Link from a Wikipage to another Wikipage
primaryTopic
Exponential search
In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. 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. This takes O(log i) where i 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.
has abstract
In computer science, an expone ...... umber of elements in the list.
@en
Wikipage page ID
42,285,695
page length (characters) of wiki page
Wikipage revision ID
967,050,463
Link from a Wikipage to another Wikipage
average-time
best-time
class
optimal
Yes
@en
space
time
wikiPageUsesTemplate
subject
hypernym
type
comment
In computer science, an expone ...... search key is not in the list.
@en
label
Exponential search
@en