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 2**. Now 2

^{k}is greater than the search key^{k}and 2

^{k-1}becomes the upper bound and lower bound for the binary search algorithm respectively.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> using namespace std; // Binary search algorithm to return the position of // target x in the sub-array A[low..high] int BinarySearch(int A[], int low, int high, int x) { // Base condition (search space is exhausted) if (low > high) return -1; // we find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // overflow can happen // int mid = low + (high - low)/2; // Base condition (target value is found) if (x == A[mid]) return mid; // discard all elements in the right search space // including the mid element else if (x < A[mid]) return BinarySearch(A, low, mid - 1, x); // discard all elements in the left search space // including the mid element else return BinarySearch(A, mid + 1, high, x); } // Returns the position of target x in the array A of length n int ExponentialSearch(int A[], int n, int x) { int bound = 1; // find the range in which the target x would reside while (bound < n && A[bound] < x) bound *= 2; // calculate the next power of 2 // call binary search on A[bound/2 .. min(bound, n)] return BinarySearch(A, bound/2, min(bound, n), x); } // main function int main() { int A[] = {2, 5, 6, 8, 9, 10}; int n = sizeof(A)/sizeof(A[0]); int target = 9; int index = ExponentialSearch(A, n, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

**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) = x^{2} + 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 🙂

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