interpolation search Algorithm
Interpolation search is an efficient algorithm for searching a specific value within a sorted array of values. This search algorithm takes advantage of the sorted nature of the array by estimating the position of the target value based on the values at the beginning and end of the array, and the relative size of the target value. The basic idea is to use the target value to calculate a likely position within the array where the value might be found, and then narrow down the search range accordingly. This approach allows the algorithm to find the target value more quickly than other search algorithms, such as linear search or binary search, especially when dealing with large arrays with uniformly distributed values.
The interpolation search algorithm starts by calculating the position of the target value using a linear interpolation formula, which involves the first and last elements of the search range, and the target value itself. This position acts as a guess for the location of the target value in the array. Based on this guess, the algorithm determines whether the target value is before, after, or at the guessed position. If the target value is found, the algorithm returns the index of the target value. If the target value is before or after the guessed position, the search range is updated accordingly, and the interpolation search process is repeated within the new search range. This process continues until the target value is found, or the search range becomes empty, indicating that the target value is not in the array. As the search range narrows down with each iteration, the interpolation search algorithm converges to the target value more rapidly than linear or binary search algorithms.
"""
This is pure Python implementation of interpolation search algorithm
"""
def interpolation_search(sorted_collection, item):
"""Pure implementation of interpolation search algorithm in Python
Be careful collection must be ascending sorted, otherwise result will be
unpredictable
:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found
"""
left = 0
right = len(sorted_collection) - 1
while left <= right:
# avoid divided by 0 during interpolation
if sorted_collection[left] == sorted_collection[right]:
if sorted_collection[left] == item:
return left
else:
return None
point = left + ((item - sorted_collection[left]) * (right - left)) // (
sorted_collection[right] - sorted_collection[left]
)
# out of range check
if point < 0 or point >= len(sorted_collection):
return None
current_item = sorted_collection[point]
if current_item == item:
return point
else:
if point < left:
right = left
left = point
elif point > right:
left = right
right = point
else:
if item < current_item:
right = point - 1
else:
left = point + 1
return None
def interpolation_search_by_recursion(sorted_collection, item, left, right):
"""Pure implementation of interpolation search algorithm in Python by recursion
Be careful collection must be ascending sorted, otherwise result will be
unpredictable
First recursion should be started with left=0 and right=(len(sorted_collection)-1)
:param sorted_collection: some ascending sorted collection with comparable items
:param item: item value to search
:return: index of found item or None if item is not found
"""
# avoid divided by 0 during interpolation
if sorted_collection[left] == sorted_collection[right]:
if sorted_collection[left] == item:
return left
else:
return None
point = left + ((item - sorted_collection[left]) * (right - left)) // (
sorted_collection[right] - sorted_collection[left]
)
# out of range check
if point < 0 or point >= len(sorted_collection):
return None
if sorted_collection[point] == item:
return point
elif point < left:
return interpolation_search_by_recursion(sorted_collection, item, point, left)
elif point > right:
return interpolation_search_by_recursion(sorted_collection, item, right, left)
else:
if sorted_collection[point] > item:
return interpolation_search_by_recursion(
sorted_collection, item, left, point - 1
)
else:
return interpolation_search_by_recursion(
sorted_collection, item, point + 1, right
)
def __assert_sorted(collection):
"""Check if collection is ascending sorted, if not - raises :py:class:`ValueError`
:param collection: collection
:return: True if collection is ascending sorted
:raise: :py:class:`ValueError` if collection is not ascending sorted
Examples:
>>> __assert_sorted([0, 1, 2, 4])
True
>>> __assert_sorted([10, -1, 5])
Traceback (most recent call last):
...
ValueError: Collection must be ascending sorted
"""
if collection != sorted(collection):
raise ValueError("Collection must be ascending sorted")
return True
if __name__ == "__main__":
import sys
"""
user_input = input('Enter numbers separated by comma:\n').strip()
collection = [int(item) for item in user_input.split(',')]
try:
__assert_sorted(collection)
except ValueError:
sys.exit('Sequence must be ascending sorted to apply interpolation search')
target_input = input('Enter a single number to be found in the list:\n')
target = int(target_input)
"""
debug = 0
if debug == 1:
collection = [10, 30, 40, 45, 50, 66, 77, 93]
try:
__assert_sorted(collection)
except ValueError:
sys.exit("Sequence must be ascending sorted to apply interpolation search")
target = 67
result = interpolation_search(collection, target)
if result is not None:
print(f"{target} found at positions: {result}")
else:
print("Not found")
