Interpolation Search | Java program to implement interpolation search with recursion ; 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 ; Driver Code ; Array of items on which search will be conducted . ; Element to be searched ; If element was found
import java . util . * ; class GFG { public static int interpolationSearch ( int arr [ ] , int lo , int hi , int x ) { int pos ; if ( lo <= hi && x >= arr [ lo ] && x <= arr [ hi ] ) { pos = lo + ( ( ( 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 ; } public static void main ( String [ ] args ) { int arr [ ] = { 10 , 12 , 13 , 16 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 33 , 35 , 42 , 47 } ; int n = arr . length ; int x = 18 ; int index = interpolationSearch ( arr , 0 , n - 1 , x ) ; if ( index != - 1 ) System . out . println ( " Element ▁ found ▁ at ▁ index ▁ " + index ) ; else System . out . println ( " Element ▁ not ▁ found . " ) ; } }