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 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 calculate the search position search_key is found if search_key is larger search_key is in upper part if search_key is smaller search_key is in lower part
from typing import List


def interpolation_search(array: List[int], search_key: int) -> int:
    

    
    high = len(array) - 1
    low = 0

    while (low <= high) and (array[low] <= search_key <= array[high]):
        
        pos = low + int(((search_key - array[low]) *
                         (high - low) / (array[high] - array[low])))

        
        if array[pos] == search_key:
            return pos

        
        if array[pos] < search_key:
            low = pos + 1

        
        else:
            high = pos - 1

    return -1


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