# 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 :

## Leave a Reply

You must be logged in to post a comment.