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.
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).
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 == 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)
12 25 43 59 61 78 92 78
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 :