Interpolation Search | If x is present in arr [ 0. . n - 1 ] , then returns index of it , else returns - 1. ; Since array is sorted , an element present in array must be in range defined by corner ; Probing the position with keeping uniform distribution in mind . ; Condition of target found ; If x is larger , x is in right subarray ; If x is smaller , x is in left subarray ; Array of items in which search will be conducted ; Element to be searched ; If element was found
def interpolationSearch ( arr , lo , hi , x ) : NEW_LINE INDENT if ( lo <= hi and x >= arr [ lo ] and x <= arr [ hi ] ) : NEW_LINE INDENT pos = lo + ( ( hi - lo ) // ( arr [ hi ] - arr [ lo ] ) * ( x - arr [ lo ] ) ) NEW_LINE if arr [ pos ] == x : NEW_LINE INDENT return pos NEW_LINE DEDENT if arr [ pos ] < x : NEW_LINE INDENT return interpolationSearch ( arr , pos + 1 , hi , x ) NEW_LINE DEDENT if arr [ pos ] > x : NEW_LINE INDENT return interpolationSearch ( arr , lo , pos - 1 , x ) NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT arr = [ 10 , 12 , 13 , 16 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 33 , 35 , 42 , 47 ] NEW_LINE n = len ( arr ) NEW_LINE x = 18 NEW_LINE index = interpolationSearch ( arr , 0 , n - 1 , x ) NEW_LINE if index != - 1 : NEW_LINE INDENT print ( " Element ▁ found ▁ at ▁ index " , index ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Element ▁ not ▁ found " ) NEW_LINE DEDENT