What is Exponential Search in Python and how to implement it

In this tutorial, we will learn about the standard Exponential search algorithm and will implement it in Python.

Exponential Search in Python

Exponential search (also called doubling search or galloping search or Struzik search) is a searching technique for sorted, unbounded/infinite lists.

There are multiple ways to perform this method, but the most common and useful one is to find the range in which the element to be searched must be present. This is done by applying a Binary Search between the ranges.

Space Complexity

Exponential Search takes constant space irrespective of the number of elements in the array taking the space required to be of the range O(1).

Time Complexity

The time complexity of the above algorithm is O(1) in the best case scenario and O(logi) in the worst case scenario; where i is the index of the element to be searched. This makes the time complexity of Exponential search to O(logi).

Implementation of Exponential search algorithm

list1=list(map(int, input().split(" ")))
val=int(input())
if list1[0] == val:
    print("0")
i = 1
#Finding range for binarySearch
while(i<len(list1) and list1[i]<=val):
        i = i * 2
min1=min(i,len(list1))
def binarySearch(data_list,low,high,value):
    if(high>= low):
        mid=int(low + ( high-low )//2)
        if data_list[mid] == value:
            return mid
        if data_list[mid] > value:
            return binarySearch(data_list,low,mid - 1,value)
        else:
            return binarySearch(data_list,mid + 1,high,value)
    if(high<low):
        return -1
    # Applying binary search for specified range
index=binarySearch(list1,i/2,min(i,len(list1)),val)
if(index==-1):
    print("Element not found")
else:
    print("Element found at ",index)

INPUT :

12 25 43 59 61 78 92
78

OUTPUT :

Element found at  5

The technique contains two parts. The first stage selects a range in which the search element would be in if it is in the list. In the second stage, a binary search is done on this range.

That’s it for now!

Drop your doubts in the comments section below.

Also, look at other searching methods :