# Exponential Search

Note

If you don’t know what is binary search, then first please go through the binary search algorithm here.

Exponential search, also known as doubling search or finger search, is an algorithm created for searching elements in huge sized arrays. It is a two-step process. First, the algorithm tries to find the range `(L, R)` in which the target element is present and then uses binary search inside this range to find the target’s exact location.

It is named exponential search because it finds the range holding element by searching for the first exponent `k` for which element at index `pow(2,k)` is greater than the target. Although its name is exponential search, the time complexity of this algorithm is logarithmic. It is very useful when arrays are of infinite size and converges to a solution much faster than binary search.

## Exponential Search Algorithm

Let us assume that we have an unsorted array `A[]` containing `n` elements, and we want to find an element `X`.

• ##### While `i < n` and `A[i] <= X` do the following:
• Increment `i` in powers of `2` i.e. `i = i*2`.

## Exponential Search Example

Suppose we have the array: `(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)`, and we want to find X - `10`.

## Exponential Search Algorithm Implementation

``````#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x)
{
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
lo = m + 1;
else
hi = m - 1;
}
return -1;
}

int exponentialSearch(int arr[], int n, int x)
{
if (arr == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i * 2;

return binarySearch(arr, i / 2,
min(i, n - 1), x);
}

int main()
{
int n = 11;
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int x = 10;
int result = exponentialSearch(arr, n, x);
if (result == -1) {
}
else cout << "Element found at index " << result;
return 0;
}
``````

## Exponential Search Algorithm Complexity

### Time Complexity

• Average Case

The average-case time complexity is `O(logi)` where `i` is the index of target element `X` inside the array. It even outperforms binary search when the element is near the beginning of the array.

• Best Case

The best-case occurs when the element we compare is the element we are searching for and is returned in the first iteration. The best-case time complexity is `O(1)`.

• Worst-Case

The worst-case time complexity is the same as the average-case time complexity. The worst-case time complexity is `O(logi)`.

### Space Complexity

This algorithm’s space complexity is `O(1)` because it doesn’t require any extra space other than temporary variables.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

## Related Article - Search Algorithm

• Interpolation Search
• Jump Search