interpolation_search.py

import math
import random

def search(array, key):
    if len(array) == 0: return -1
    hits = 0
    max_value = 4294967296
    min_value = 0
    lower = 0
    upper = len(array) - 1

    index = math.floor((key - min_value) / (max_value - min_value) * (upper - (lower + 1))) + lower
    while True:
        hits += 1
        value = array[int(index)]
        if value > key:
            upper = index - 1
            max_value = value
        elif value < key:
            lower = index + 1
            min_value = value
        elif value == key:
            return hits, index
        if upper < lower:
            return hits, -1 * lower - 1
        index = math.floor((key - min_value) / (max_value - min_value)  * (upper - (lower + 1))) + lower

def generate(N):
    return sorted([random.random() for i in range(N)])

def expected_hits(N):
    t = generate(N)
    expected = 0
    tests = 1000
    for _ in range(1, tests):
        index = int(random.uniform(0, N - 1))
        key = t[index]
        hits, found_index  = search(t, key)
        assert t[found_index] == key
        expected += hits
    return expected / tests

if __name__ == "__main__":
    for N in range(1, 1000000000, 10):
        hits = expected_hits(N)
        print (f"N {hits}")