// C program to implement interpolation search
// with recursion
#include 
 
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int lo, int hi, int x)
{
    int pos;
    // Since array is sorted, an element present
    // in array must be in range defined by corner
    if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
        // Probing the position with keeping
        // uniform distribution in mind.
        pos = lo
              + (((double)(hi - lo) / (arr[hi] - arr[lo]))
                 * (x - arr[lo]));
 
        // Condition of target found
        if (arr[pos] == x)
            return pos;
 
        // If x is larger, x is in right sub array
        if (arr[pos] < x)
            return interpolationSearch(arr, pos + 1, hi, x);
 
        // If x is smaller, x is in left sub array
        if (arr[pos] > x)
            return interpolationSearch(arr, lo, pos - 1, x);
    }
    return -1;
}
 
// Driver Code
int main()
{
    // Array of items on which search will
    // be conducted.
    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; // Element to be searched
    int index = interpolationSearch(arr, 0, n - 1, x);
 
    // If element was found
    if (index != -1)
        printf("Element found at index %d", index);
    else
        printf("Element not found.");
    return 0;
}                         
                            
                          
                               
                        
                         Code 
                    

                        
// Java program to implement interpolation
// search with recursion
import java.util.*;
 
class GFG {
 
    // If x is present in arr[0..n-1], then returns
    // index of it, else returns -1.
    public static int interpolationSearch(int arr[], int lo,
                                          int hi, int x)
    {
        int pos;
 
        // Since array is sorted, an element
        // present in array must be in range
        // defined by corner
        if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
 
            // Probing the position with keeping
            // uniform distribution in mind.
            pos = lo
                  + (((hi - lo) / (arr[hi] - arr[lo]))
                     * (x - arr[lo]));
 
            // Condition of target found
            if (arr[pos] == x)
                return pos;
 
            // If x is larger, x is in right sub array
            if (arr[pos] < x)
                return interpolationSearch(arr, pos + 1, hi,
                                           x);
 
            // If x is smaller, x is in left sub array
            if (arr[pos] > x)
                return interpolationSearch(arr, lo, pos - 1,
                                           x);
        }
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Array of items on which search will
        // be conducted.
        int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                      22, 23, 24, 33, 35, 42, 47 };
 
        int n = arr.length;
 
        // Element to be searched
        int x = 18;
        int index = interpolationSearch(arr, 0, n - 1, x);
 
        // If element was found
        if (index != -1)
            System.out.println("Element found at index "
                               + index);
        else
            System.out.println("Element not found.");
    }
}                          
    
                        
                         Code 
                    

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

                        
                         Code