Binary search is based on the logic that it focuses on the middle section of the data. Interpolation search is more sophisticated. It uses the target value to estimate the position of the element in the sorted array. Let's try to understand it by using an example. Let's assume we want to search for a word in an English dictionary, such as the word river. We will use this information to interpolate and start searching for words starting with r. A more generalized interpolation search can be programmed as follows:

def IntPolsearch(list,x ):     
    idx0 = 0     
    idxn = (len(list) - 1)     
    found = False     
    while idx0 <= idxn and x >= list[idx0] and x <= list[idxn]: 
    # Find the mid point         
         mid = idx0 +int(((float(idxn - idx0)/( list[idxn] - list[idx0])) * ( x - list[idx0]))) 
 # Compare the value at mid point with search value 
         if list[mid] == x: 
            found = True             
            return found         
    if list[mid] < x:             
            idx0 = mid + 1     
return found

The output is as follows:

Note that before using IntPolsearch, the array first needs to be sorted using a sorting algorithm.