Here, we are going to learn what is Exponential Search and its algorithm, its time complexity, and why to use the Exponential Search.

The prerequisite for searching an element through Exponential Search is that the array of elements should be arranged in an ascending order. Let's first see the input and output and then accordingly go for its algorithm:

Search the element 4:

Input : arr = [1,2,3,4,5]

Output: Element 4 is at index 3

Search the element 10:

Input : arr = [5,10,15,20,25]

Output: Element 10 is at index 1

Search the element 99:

Input : arr = [3,20,55,99]

Output: Element 99 is at index 3

- Find the subarray in which the element to be found is present.
- Do a Binary Search on the subarray found in the first step.

**arr = [1,2,3,4,5,6,7,8,9,10,11,12]**and we have to search for element 11, lets term it as

`x`

. We will first see that the element is present at the start that is the first position itself `arr[0] == x`

, if yes, then return the index 0. But, if not then, we will run a while loop from index 1 till the end of the array with the condition such as:```
i = 1
while i < n and arr[i] <= x:
i = i * 2
```

Let's see how the value of `i `

increments and what happens at each iteration:

For the above example,* x = 11*(element to be searched), *n = 12*(length of array)

when i =1, `1 < n`

is True, `arr[1] <= x`

is True

`i = 1 * 2`

= 2

now, i = 2, `2 < n`

is True, `arr[2] <= x`

is True

`i = 2 * 2`

= 4

now, i = 4, `4 < n`

is True, `arr[4] <= x`

is True

` i = 4 * 2`

= 8

now, i = 8, `8 < n`

is True, `arr[8] <= x`

is True

`i = 8 * 2`

= 16

now, i = 16, `16 < n`

is False, hence we come out of the `while `

loop.

Here comes the second step of the algorithm that is the **Binary Search**.

Remember that from the while loop we got i =16. We will always do Binary search from `i/2`

till `min(i, n-1)`

. Here `i/2 = 8`

and `min(16, 12-1) = 11`

We do` i/2`

because we got the value of i as *16 *which does not satisfy the condition but before this step, the value of `i `

was *8 *which satisfied all the conditions, hence we do` i/2`

.

But why `min(i, n-1)`

? Simply because we do want to go beyond the length of the array. There could be a case where, the value of `i `

after coming out of the `while `

loop would be `i = 16`

and the length of the input array can be `20`

. So if do `min(i, n-1)`

that is `min(16, 20-1) = 16.`

So, now we got the subarray from our input array that is from `i = 8 to i = 11`

which is** [9, 10, 11, 12].** We will simply do a Binary search on this subarray instead of the entire array with the low value as `i/2`

and high value as `min(i, n-1)`

:

```
binary_search(arr, i/2, min(i, n-1), x)
```

*Note: that the elements of the array should be in ascending order everytime to do Binary search.*

Binary Search follows the Divide and Conquer rule. It works as:

- Compare
`x`

with the middle element of the given array. - If
`x`

matches with middle element, then we return the mid index. - Else if
`x`

is greater than the mid element, then x can only lie in right half subarray after the mid element. So we iterate only on the right half of the given array. - Else if
`x`

is smaller than the mid element, then we iterate only on the left half of the given array.

` mid = (8 + 11) / 2 = 9`

. As `arr[9] = 10 `

and 10< 11(the number to be searched), we iterate right part of the mid element that is from index 10 to index 11.`mid = (10 + 11) / 2 = 10`

As `arr[10] =11`

which is the element we want. Yay! we found it at index 10.`i `

as `i = i * 2.`

To be more precise, we incremented it exponentially:^{0}

^{1}

^{2}

^{3}

^{4}

```
def bin_search(arr, low, high, x):
if high >= low:
mid = low + (high - low) // 2
if arr[mid] == x:
return mid
if arr[mid] > x:
return bin_search(arr, low, mid - 1, x)
return bin_search(arr, mid + 1, high, x)
return -1 # if element is not present, return -1
def exponential_search(arr, n, x):
if arr[0] == x:
return 0
i = 1
while i < n and arr[i] <= x:
i = i * 2
return bin_search(arr, i // 2, min(i, n - 1), x)
# Driver Code
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
n = len(arr)
x = 11
res = exponential_search(arr, n, x)
if res == -1:
print(f"The element {x} is not present in the array ")
else:
print(f"The element {x} is is present at index {res} ")
```

The element 11 is is present at index 10

We are passing the input array `arr`

, length of array `n`

, and element to be found `x `

to the function `exponential_search()`

.

- We check if the element lies at first position
`if arr[0] == x`

, then return the index 0 - If not, run the
`while`

loop , from`i = 1`

,`while i < n and arr[i] <= x.`

- If the condition of
`while`

loop is True, exponentially increment the value of i`i = i * 2`

- As discussed above, after call the function
`bin_search()`

with low value as`i/2`

and high value as`min(i, n - 1)`

as discussed before the implementation of the algorithm. - By doing the Binary search we find the index of the element and return it, if element not found, we return -1.

## Performance of Exponential Search

In the first part of the algorithm, we are jumping by a factor of 2 at each step (2, 4, 8, 16, and so on). In the worst case, it can go upto n (length of the array). So, it will run in $O(\lg{n})$. The second part is simply a binary search, it will also take $O(\lg{n})$. Thus, the time complexity of the algorithm is $O(\lg{n})$ ($O(\lg{n})+O(\lg{n})$).

The Space Complexity is:

a) `O(1)`

- If we find the element with * iterative *binary search

b) `O(logn) extra space `

- If we find the element with * recursive *binary search

## Why to use Exponential Search:

- It is useful for unbounded arrays that is arrays with very large size.
- It is better than Binary search because instead of doing a Binary search on the entire array, here, we first find the subarray and then do the Binary search on it. So, if we think logically, Exponential search is better than Binary search.