Interpolation Search

interpolation_search.py

# From http://data.linkedin.com/blog/2010/06/beating-binary-search

def interpolation_search(key, array, min, max):
    """
    Interpolation search.
    >>> a = [7, 28, 28, 41, 45, 50, 59, 68, 74, 96]
    >>> k = 59
    >>> print interpolation_search(k, a, 0, 99)
    6
    """
    low = 0
    high = len(array) - 1
    while True:
        if low > high or key < min or key > max:
            return -1
        if high == low:
            guess = high;
        else:
            size = high - low
            offset = (size * (key - min)) / (max - min)
            guess = low + offset
        if array[guess] == key:
            return guess
        if guess == 0 or guess == (len(array) - 1):
            return -1
        if array[guess] > key:
            high = guess - 1
            max = array[guess - 1]
        else:
            low = guess + 1
            min = array[guess + 1]