# Exponential Search

The term Exponential generally denotes rapid growth, and mathematically it means increasing in powers.

For example:

• Exponential growth of 2: 2^0, 2^1, 2^2, 2^3, 2^4 and so on => (1, 2, 4, 8, 16,…..)

• Exponential growth of 3: 3^0, 3^1, 3^2, 3^3, 3^4 and so on => (1, 3, 9, 27, 81,….)

We use the same generated numbers ( powers of 2 ) to jump indexes in array and get closer to the index of key.

In this algorithm, ultimately we rely on Binary Search for searching, but before that, we finalize a range in which the element we want to search might be present.

To finalize this range we follow a certain algorithm, let’s have a quick look at the overview of working of this algorithm with the help of an example.

Consider a sorted Array: `7 12 34 57 65 74 81 88 89 93 100`

Element to search: `93` We will start by comparing the first element of the array with the key.

But `Array=7`, which is not equal to `93`.

Now we will take a variable whose value will increase exponentially, hence the name, `exponential search.`

`int i= 1` ( because `2^0=1`)

Now we will see if `Array[i]` is less than or equal to the key.

If it is, then we will keep on increasing the value exponentially.

`i=i*2`

This will generate values in powers of 2. `( 2, 4, 8, 16, 32...)`

We will keep on increasing the value of `i`, until the condition `Array[i]<=key` is satisfied.

So in the above example, the value of `i` will reach `8` (in the actual code it will reach 16, then we will divide it by 2) and the sub-array after this index will be selected (including the index of `i`), and then the binary search will be applied to this range.

## Exponential Search Algorithm

There are majorly two steps included in implementing exponential search:-

1. Finding the range in which the key might lie
2. Applying binary search in this range

#### Steps

• Start with value `i=1`
• Check for condition `i < n` and `Array[i]<=key`, where `n` is the number of elements in the array and key is the element being searched
• Increment value of i in powers of 2, that is, `i=i*2`
• Keep on incrementing the value of `i` until the condition is satisfied
• Apply binary on the range `i/2` till the end of Array - `binarySearch(Array, i/2, min(i,n-1))`

## Example

Consider the array:- `1 3 5 7 9 11 13 15 17 19`

Element to search: `19` • We will start by comparing `Array` element to key, which in our case would return false.
• `i` will be initialized to `1`

Now we will keep on incrementing the value of `i` until it is less than or equal to the key

``````After 1st pass i will be 2 - condition satisfied
After 2nd pass i will be 4 - condition satisfied
After 3rd pass i will be 8 - condition satisfied
After 4th pass i will be 16 - CONDITION FAILED``````

Note that the value of i is now `16`, and the index `16` is out of range in this case, so to get the previous value of `i` we will divide it by `2`, and call binary search using index of `low` as `i/2`.

Now we call the binary search method.

`binarySearch(Array, i/2, min(i, n-1), key)` ``````low = 8, high = 10

mid = (low + high)/2

= 18/2

= 9``````

`Array=19`, which is the required element.

Now let’s have a look at the Java code for the same.

## Code

``````public class Searching {

boolean exponentialSearch(int arr[], int key) {

int lengthOfArray = arr.length;

if (arr == key) { // Checking whether first element is the key
return true;
}

// Finding the range in which the element might be present

int i = 1;

while (i < lengthOfArray && arr[i] <= key) {
i = i * 2; // Exponentially increasing value of i.

}

return binarySearch(arr, i / 2, Math.min(i, lengthOfArray - 1), key); // calling binary search method on the sub-array

}

boolean binarySearch(int arr[], int low, int high, int key) {

int mid; // to store middle element

while (low <= high) {

mid = (low + high) / 2; // we can also do mid = low+(high-low)/2 to avoid overflow in some cases

if (arr[mid] == key) {
return true;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}

// Driver Code

public static void main(String args[]) {

Searching search = new Searching();

int arr[] = {
1,
3,
4,
6,
8,
13,
15,
24
};

if (search.exponentialSearch(arr, 15)) {
System.out.println("Element found !");
} else {
System.out.println("Element not found :( ");
}

}

}``````

## Performance

CaseRuntime
BestO(1)
AverageO(log i)
WorstO(log i)
Auxiliary SpaceO(1)

Here `i` is the index of the key.

Exponential search is useful in cases where the arrays are unbounded or of infinite size and can converge to the solution much faster than binary search in these cases.