collection if match occursthen the index of the item is returned if the middle item is greater than the itemthen the probe position is again calculated in the sub-array to the right of the middle item otherwisethe item is searched in the subarray to the left of the middle item this process continues on the sub-array as well until the size of subarray reduces to zero there is specific formula to calculate the middle positionwhich is indicated in the program belowdef intpolsearch(values, )idx idxn (len(values while idx values[idx and <values[idxn]find the mid point mid idx +int(((float(idxn idx )/values[idxnvalues[idx ]) values[idx ]))compare the value at mid point with search value if values[mid=xreturn "found "+str( )+at index "+str(midif values[midxidx mid return "searched element not in the listl [ print(intpolsearch( )when the above code is executedit produces the following resultfound at index