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.
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: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 , fromi = 1
,while i < n and arr[i] <= x.
- If the condition of
while
loop is True, exponentially increment the value of ii = i * 2
- As discussed above, after call the function
bin_search()
with low value asi/2
and high value asmin(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.