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 sub array ; If x is smaller , x is in left sub array ; Array of items on which search will be conducted . ; Element to be searched ; If element was found
function interpolationSearch ( arr , lo , hi , x ) { let pos ; if ( lo <= hi && x >= arr [ lo ] && x <= arr [ hi ] ) { pos = lo + Math . floor ( ( ( hi - lo ) / ( arr [ hi ] - arr [ lo ] ) ) * ( x - arr [ lo ] ) ) ; ; if ( arr [ pos ] == x ) { return pos ; } if ( arr [ pos ] < x ) { return interpolationSearch ( arr , pos + 1 , hi , x ) ; } if ( arr [ pos ] > x ) { return interpolationSearch ( arr , lo , pos - 1 , x ) ; } } return - 1 ; } let arr = [ 10 , 12 , 13 , 16 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 33 , 35 , 42 , 47 ] ; let n = arr . length ; let x = 18 let index = interpolationSearch ( arr , 0 , n - 1 , x ) ; if ( index != - 1 ) { document . write ( ` ${ index } ` ) } else { document . write ( " " ) ; }