PYTHON

interpoltaion search formula python

array = [5, 8, 10, 14, 22, 28, 33, 36, 39, 42, 45, 50]

# top is the upper index of the array segment we are searching, initially n = 1 or n.
top = (len(array) - 1)
print("This is top: " + str(top))

# bottomis the lower index of the array segment we are searching, intitially 0 or 1.
bottom = 0
print("This is bottom: " + str(bottom))

# Vbottom is the value in the array at index *bottom*.
Vbottom = array[bottom]
print("this is Vbottom: " + str(Vbottom))

# Vtop is the value in the array at index *top*.
Vtop = array[top]
print("this is Vtop: " + str(Vtop))

# k is the key of the item that we are seeking(i.e., the search target).
k = int(input("What is the key of the item? "))
print("This is the item we are seeking " + str(k))

# i is the array index predicted to contain key k.
i = 0


# Python3 program to implement
# interpolation search
# with recursion

# If x is present in arr[0..n-1], then
# returns index of it, else returns -1.


def interpolationSearch(arr, lo, hi, x):
    # Since array is sorted, an element present
    # in array must be in range defined by corner
    if lo <= hi and arr[lo] <= x <= arr[hi]:

        # Probing the position with keeping
        # uniform distribution in mind.
        TopBottom = hi - lo
        kVbottom = x - arr[lo]
        VtopVbottom = arr[hi] - arr[lo]
        kVbottomDividedVtopVbottom = kVbottom / VtopVbottom
        pos = TopBottom * kVbottomDividedVtopVbottom + lo
        print(pos)
        pos = int(pos)
        print(pos)

        # Condition of target found
        if arr[pos] == x:
            print("found " + str(pos))
            return pos

        # If x is larger, x is in right subarray
        if arr[pos] < x:
            print("bigger " + str(pos))
            return interpolationSearch(arr, pos + 1,
                                       hi, x)

        # If x is smaller, x is in left subarray
        if arr[pos] > x:
            print("smaller " + str(pos))
            return interpolationSearch(arr, lo,
                                       pos - 1, x)
    return -1


# Driver code

index = interpolationSearch(array, bottom, top, k)

if index != -1:
    print("Element found at index", index)
else:
    print("Element not found")

# This code is contributed by Hardik Jain