# Exponential Search Algorithm

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

Exponential search algorithm (also called doubling search, galloping search, Struzik search) is a search algorithm, created by *Jon Bentley* and *Andrew Chi-Chih Yao* in 1976, for searching sorted, unbounded/infinite lists.

### Algorithm

Exponential search involves two basic steps:

- Find range where element is present
- Execute Binary Search algorithm in above found range.

** How to find the range where element may be present? **

The idea is to start with sub-list of size 1. Ccompare the last element of the list with the target element, then try size 2, then 4 and so on until last element of the list is not greater.

Once we find a location `loc`

(after repeated doubling of list size), we know that the element must be present between `loc/2`

and `loc`

.

### Complexity

- Worst case time complexity:
`O(log i)`

where i is the index of the element being searched. - Average case time complexity:
`O(log i)`

- Best case time complexity:
`O(1)`

- Space complexity:
`O(1)`

### Implementations

Implementation of exponential search algorithm in 9 languages that includes `C`

, `C++`

, `Java`

, `Go`

, `JavaScript`

, `PHP`

, `Python`

, `Rust`

and `Swift`

.

- C
- C++

### C

```
#include <stdio.h>
int
min(int a, int b)
{
return (a < b ? a : b);
}
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
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
main()
{
int n;
printf("Enter size of Array \n");
scanf("%d", &n);
int arr[n], i;
printf("Enter %d integers in ascending order \n", n);
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);
int x;
printf("Enter integer to be searched \n");
scanf("%d", &x);
int result = exponentialSearch(arr, n, x);
if (result == -1)
printf("%d is not present in array \n", x);
else
printf("%d is present at index %d \n", x, result);
return (0);
}
```

### C++

```
// C++ program to find an element x in a
// sorted array using Exponential search.
#include <cstdio>
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int binarySearch(int arr[], int, int, int);
// Returns position of first ocurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
// If x is present at firt location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return binarySearch(arr, i/2, min(i, n), x);
}
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
// can only be present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
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;
}
```

### Applications

- Exponential Binary Search is useful for unbounded searches where size of array is infinite.
- It works better than Binary Search for bounded arrays when the element to be searched is closer to the beginning of the array.