Python implementation of the Interpolation Search algorithm. Given a sorted array in increasing order, interpolation search calculates the starting point of its search according to the search key. FORMULA: startpos  low   x  arrlowhigh  low  arrhigh  arrlow  Doc: https:en.wikipedia.orgwikiInterpolationsearch Time Complexity: Olog2log2 n for average cases, On for the worst case. The algorithm performs best with uniformly distributed arrays. :param array: The array to be searched. :param searchkey: The key to be searched in the array. :returns: Index of searchkey in array if found, else 1. Examples:  interpolationsearch25, 12, 1, 10, 12, 15, 20, 41, 55, 1 2  interpolationsearch5, 10, 12, 14, 17, 20, 21, 55 1  interpolationsearch5, 10, 12, 14, 17, 20, 21, 5 1 highest and lowest index in array calculate the search position searchkey is found if searchkey is larger, searchkey is in upper part if searchkey is smaller, searchkey is in lower part
from typing import List


def interpolation_search(array: List[int], search_key: int) -> int:
    """
    :param array: The array to be searched.
    :param search_key: The key to be searched in the array.

    :returns: Index of search_key in array if found, else -1.

    Examples:

    >>> interpolation_search([-25, -12, -1, 10, 12, 15, 20, 41, 55], -1)
    2
    >>> interpolation_search([5, 10, 12, 14, 17, 20, 21], 55)
    -1
    >>> interpolation_search([5, 10, 12, 14, 17, 20, 21], -5)
    -1

    """

    # highest and lowest index in array
    high = len(array) - 1
    low = 0

    while (low <= high) and (array[low] <= search_key <= array[high]):
        # calculate the search position
        pos = low + int(((search_key - array[low]) *
                         (high - low) / (array[high] - array[low])))

        # search_key is found
        if array[pos] == search_key:
            return pos

        # if search_key is larger, search_key is in upper part
        if array[pos] < search_key:
            low = pos + 1

        # if search_key is smaller, search_key is in lower part
        else:
            high = pos - 1

    return -1


if __name__ == "__main__":
    import doctest
    doctest.testmod()
