In computer science, an exponential search (also named 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. exponential search can even out-perform more traditional searches for bounded lists, such as binary search, when the component being searched for is near the beginning of the array.

If the component at the current index is larger than the search key, the algorithm now knows that the search key, if it is contained in the list at all, is located in the interval formed by the previous search index, 2j-1, and the current search index, 2j. exponential search lets for searching through a sorted, unbounded list for a specified input value (the search" key"). As such, the first phase of the algorithm takes O(logThe second part of the algorithm also takes O(log

```
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int, int, int);
int exponentialSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
return binarySearch(arr, i/2, min(i, n), x);
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}
```