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 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
else:
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)
Output:
Index position of value 75 is 2
DSA
Python
Comments
Post a Comment