Interpolation Search Algorithm in Python

In this source code example, we will write a code to implement the Interpolation Search algorithm in Python.

Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values assigned to the keys (key values). It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered.

Interpolation Search Algorithm in Python

def nearest_mid(input_list, lower_bound_index, upper_bound_index, search_value):
    return lower_bound_index + (( upper_bound_index - lower_bound_index)// (input_list[upper_bound_index] - input_list[lower_bound_index])) * (search_value - input_list[lower_bound_index])

def interpolation_search(ordered_list, term):
    size_of_list = len(ordered_list) - 1
    index_of_first_element = 0
    index_of_last_element = size_of_list
    while index_of_first_element <= index_of_last_element:
        mid_point = nearest_mid(ordered_list, index_of_first_element, index_of_last_element, term)
        if mid_point > index_of_last_element or mid_point < index_of_first_element:
            return None
        if ordered_list[mid_point] == term:
            return mid_point
        if term > ordered_list[mid_point]:
            index_of_first_element = mid_point + 1
            index_of_last_element = mid_point - 1

store = [10,20,75,30,25,35,40]
a = interpolation_search(store, 75)
print("Index position of value 75 is ", a)


Index position of value 75 is  2