VietMX Staff asked 3 years ago
Exponential Search (also called Doubling Search or Galloping Search or Struzik Search) is explicitly designed for sorted, unbounded lists (infinite arrays or arrays with unknown size) whereas binary search deals with bounded lists (size is known).
It has two steps:
- Search for a position of first element greater or equal than the target value. Assuming that the list is sorted in ascending order, the algorithm looks for the first exponent,
j, where the valuearr(2j)is greater than the search key (target value). 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. - Do the binary search from the beginning to the found end
Complexity Analysis
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. 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. 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).
Implementation
function exponentialSearch(arrayToSearch, valueToSearch){
if (arrayToSearch[0] == valueToSearch){
return 0;
}
var i = 1;
while (i < arrayToSearch.length && arrayToSearch[i] <= valueToSearch){
i = i*2;
}
return binarySearch(arrayToSearch, valueToSearch);
}