interpolation_search.py

# 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.



definterpolationSearch(arr, lo, hi, x):


# Since array is sorted, an element present

# in array must be in range defined by corner

if (lo<=hiandx>=arr[lo] andx<=arr[hi]):


# Probing the position with keeping

# uniform distribution in mind.

pos=lo+ ((hi-lo) // (arr[hi] -arr[lo]) *

 (x-arr[lo]))


# Condition of target found

ifarr[pos] ==x:

returnpos


# If x is larger, x is in right subarray

ifarr[pos] <x:

returninterpolationSearch(arr, pos+1,

hi, x)


# If x is smaller, x is in left subarray

ifarr[pos] >x:

returninterpolationSearch(arr, lo,

pos-1, x)

return-1

# Driver code


# Array of items in which
# search will be conducted

arr= [10, 12, 13, 16, 18, 19, 20,

21, 22, 23, 24, 33, 35, 42, 47]

n=len(arr)

# Element to be searched

x=18

index=interpolationSearch(arr, 0, n-1, x)


ifindex!=-1:

print("Element found at index", index)

else:

print("Element not found")