BlogsDope image BlogsDope

Exponential Search

Feb. 21, 2021 PYTHON ALGORITHM DATA STRUCTURE 178

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

The Exponential Search focuses on two major things:
  1. Find the subarray in which the element to be found is present. 
  2. Do a Binary Search on the subarray found in the first step.
Let's see the first step where we concentrate on finding the subarray where the element lies. In this step, the finding of the subarray happens exponentially. Let's see what does this mean:
If the input array is: 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:

Sorted array

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:

  1. Compare x with the middle element of the given array. 
  2. If x matches with middle element, then we return the mid index. 
  3. 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.
  4. Else if x is smaller than the mid element, then we iterate only on the left half of the given array.
Let's see how it works for our above example. The subarray for the Binary search is:
Here, 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.
Now, mid = (10 + 11) / 2 = 10 As arr[10] =11 which is the element we want. Yay! we found it at  index 10.
Can we now guess why this algorithm is termed as Exponential Search? I hope till now you have got the reason behind it. If not, let me tell you:
Did you notice that while finding the subarray in the first step of the algorithm, in the while loop, we incremented the value of i as i = i * 2. To be more precise, we incremented it exponentially:
i =1 = 20
i = 1 * 2 = 2 = 21
i = 2 * 2 = 4 = 22
i = 4 * 2 = 8 = 23
i = 8 * 2 = 16 = 24
Let's see the actually implementation of the algorithm:​
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().

  1. We check if the element lies at first position if arr[0] == x, then return the index 0
  2. If not, run the while loop , from i = 1while i < n and arr[i] <= x.
  3. If the condition of while loop is True, exponentially increment the value of i i = i * 2 
  4. 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.
  5. 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:

  1. It is useful for unbounded arrays that is arrays with very large size.
  2. 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.

Liked the post?
Rarely seen, always noticed.
Editor's Picks
0 COMMENT

Please login to view or add comment(s).