Exponential search

Given a sorted array of integers and a target value, find out if a target exists in the array or not in O(log(n)) time. If target exists in the array, print index of it.


For example,


Input: A[] = [2, 3, 5, 7, 9]
target = 7

Output: Element found at index 3
 

Input: A[] = [1, 4, 5, 8, 9]
target = 2

Output: Element not found
 

Prerequisites: Binary Search Algorithm
 


 
Exponential search is an algorithm used for searching sorted, unbounded/infinite arrays. The idea is to determine a range that the target value resides in and perform a binary search within that range. Assuming that the array is sorted in ascending order, it looks for the first exponent k, where the value 2k is greater than the search key. Now 2k and 2k-1 becomes the upper bound and lower bound for the binary search algorithm respectively.

 
C++ implementation –
 

Download   Run Code

Output:

Element found at index 4

 

Performance

Exponential search takes O(log(i)) time where i is the position of the target in the array, if the target is in the array, or the position where the target should be, if it is not in the array.

Exponential search can also be used to search in bounded arrays. It can even out-perform binary search, when the target 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 array, whereas binary search would run in O(log(n)) time, where n is the number of elements in the array.

 
Exercise:
Find where a strictly increasing function (f(x) > f(x-1) for all values of x) becomes positive for the first time. Consider f(x) = x2 + 2x – 400. It becomes positive for first time for x = 20
 

References: https://en.wikipedia.org/wiki/Exponential_search
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Nishant
Guest
Nishant

Thank you! It is always good to know about new, interesting algorithms..

wpDiscuz