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 :

Implementing Jump Search algorithm in Python

What is Exponential Search in Python and how to implement it



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.

Space Complexity

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).


Time Complexity

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")

INPUT :

10 12 13 16 18 19 20 22 23 24 33 35 42 47
24

 

OUTPUT :

9

 

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,

Leave a Reply

Your email address will not be published. Required fields are marked *