Implementing Interpolation Search algorithm in Python
In this tutorial, we will learn about the standard Interpolation search algorithm in Python and will implement it in Python.
Also, have a look at other searching algorithms :
Interpolation Search in Python
Interpolation search is an algorithm first described by W. W. Peterson in 1957.
This Search algorithm is an advancement over Binary Search but it comes alongside with increased restriction of having the values to be uniformly distributed in the array. This algorithm will only work if the difference between key values would be similar for all elements because it works on approximation.
How Interpolation Search works ?
Unlike Binary Search, which always start checking from the middle element in the list; but Interpolation search may start from any random position.
Interpolation works much similar to the pattern people search for Phone Numbers in the directory; going near about the value to be searched for and then perform a consecutive search to find the exact value near about that location.For example, if the value to be found is near the end of the list; rather than going to the middle element, the interpreter would start searching about at 3/4 values from the start because it would eventually reduce the number of comparisons.
Jump Search takes constant space irrespective of the number of elements in the array; so making the space required to be of the range O(1).
The time complexity of the above algorithm is O(log(logn)), where n is the number of elements in the list; and in the worst case scenario it may end up taking time complexity of O(n) similar to linear search.
Code to implement Interpolation Search
list1=list(map(int ,input().split())) val=int(input()) start=0 end=len(list1)-1 flag=0 while(start<=end and val>=list1[start] and val<=list1[end]): if(start==end): if list1[start] == val: print(start) flag=1 else: print("-1") random= start + int(((float(end-start)/(list1[end]-list1[start]))*(val-list1[start]))) if list1[random]==val: print(random) flag=1 if list1[random]<val: start= random+1 else: end= random-1 if(flag==0): print("-1")
10 12 13 16 18 19 20 22 23 24 33 35 42 47 24
That’s it ! See you in the next post
Feel free to drop any queries in the comments section below
Also have a look at,
- Linear search: What it is and how to implement it in python
- How to implement Breadth First Search algorithm in Python