Exponential search

Exponential search
ClassSearch algorithm
Data structureArray
Worst-case performanceO(log i)
Best-case performanceO(1)
Average performanceO(log i)
Worst-case space complexityO(1)
OptimalYes

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. 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.

Exponential search can also be used to search in bounded lists. Exponential search can even out-perform more traditional searches for bounded lists, such as binary search, when the element being searched for is near the beginning of the array. This is because exponential search will run in O(log i) time, where i is the index of the element being searched for in the list, whereas binary search would run in O(log n) time, where n is the number of elements in the list.

  1. ^ Cite error: The named reference Baeza-Yates was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference PaperBentley was invoked but never defined (see the help page).

Exponential search

Dodaje.pl - Ogłoszenia lokalne