text: Interpolation Search | C 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
code: #include <stdio.h> NEW_LINE int interpolationSearch ( int arr [ ] , int lo , int hi , int x ) { int pos ; if ( lo <= hi && x >= arr [ lo ] && x <= arr [ hi ] ) { pos = lo + ( ( ( double ) ( 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 ; } int main ( ) { int arr [ ] = { 10 , 12 , 13 , 16 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 33 , 35 , 42 , 47 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int x = 18 ; int index = interpolationSearch ( arr , 0 , n - 1 , x ) ; if ( index != -1 ) printf ( " Element ▁ found ▁ at ▁ index ▁ % d " , index ) ; else printf ( " Element ▁ not ▁ found . " ) ; return 0 ; }