this is pure python implementation of interpolation search algorithm pure implementation of interpolation search algorithm in python be careful collection must be ascending sorted otherwise result will be unpredictable param sortedcollection 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 out of range check 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 left0 and rightlensortedcollection1 param sortedcollection 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 out of range check 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 assertsorted0 1 2 4 true assertsorted10 1 5 traceback most recent call last valueerror collection must be ascending sorted userinput input enter numbers separated by comma n strip collection intitem for item in userinput split try assertsortedcollection except valueerror sys exit sequence must be ascending sorted to apply interpolation search targetinput input enter a single number to be found in the list n target inttargetinput 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 avoid divided by 0 during interpolation out of range check 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 out of range check 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 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
def interpolation_search(sorted_collection, item):
    
    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        
        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]
        )

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

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

    
    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):
    
    if collection != sorted(collection):
        raise ValueError("Collection must be ascending sorted")
    return True


if __name__ == "__main__":
    import sys

    

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