Question

How to implement interpolation search in Python

Answer 1

def interpolation_search(arr,  item) :
    low = 0
    high = len(arr) - 1
    mid = -1
    index = -1
    while (low <= high) :
        mid = low + ((int((high - low) / (arr[high] - arr[low]))) * (item - arr[low]))
        if (arr[mid] == item) :
            index = mid
            break
        else :
            if (arr[mid] < item) :
                low = mid + 1
            else :
                high = mid - 1
    return index

arr = [2, 5, 6, 8, 9, 12, 20, 30, 34, 36, 40, 46, 50, 51, 55, 61, 72, 86, 97]
item = 51

index = interpolation_search(arr, item)

if (index != -1) :
    print("index = " + str(index), end ="")
else :
    print("Not found", end ="")
    
    
    
'''
run:

index = 13

'''
    

 

70+ SQL courses for beginners and professionals