// C++ program to implement interpolation // search with recursion #include    using namespace std; // 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]);  // Element to be searched  int x = 18;  int index = interpolationSearch(arr 0 n - 1 x);  // If element was found  if (index != -1)  cout << 'Element found at index ' << index;  else  cout << 'Element not found.';  return 0; } // This code is contributed by equbalzeeshan 

// 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; } 

// 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.');  } } // This code is contributed by equbalzeeshan 

# 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') # This code is contributed by Hardik Jain 

// C# program to implement  // interpolation search using System; class GFG{ // If x is present in  // arr[0..n-1] then  // returns index of it  // else returns -1. 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()  {    // Array of items on which search will   // be conducted.   int []arr = new int[]{ 10 12 13 16 18   19 20 21 22 23   24 33 35 42 47 };    // Element to be searched   int x = 18;   int n = arr.Length;  int index = interpolationSearch(arr 0 n - 1 x);    // If element was found  if (index != -1)  Console.WriteLine('Element found at index ' +   index);  else  Console.WriteLine('Element not found.'); } } // This code is contributed by equbalzeeshan 

<script> // Javascript program to implement Interpolation Search // If x is present in arr[0..n-1] then returns // index of it else returns -1. function interpolationSearch(arr lo hi x){  let 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 + Math.floor(((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 let arr = [10 12 13 16 18 19 20 21   22 23 24 33 35 42 47]; let n = arr.length; // Element to be searched let x = 18 let index = interpolationSearch(arr 0 n - 1 x); // If element was found if (index != -1){  document.write(`Element found at index ${index}`) }else{  document.write('Element not found'); } // This code is contributed by _saurabh_jaiswal </script> 

 // PHP program to implement $erpolation search // with recursion // If x is present in arr[0..n-1] then returns // index of it else returns -1. function interpolationSearch($arr $lo $hi $x) { // 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 = (int)($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 // Array of items on which search will // be conducted. $arr = array(10 12 13 16 18 19 20 21 22 23 24 33 35 42 47); $n = sizeof($arr); $x = 47; // Element to be searched $index = interpolationSearch($arr 0 $n - 1 $x); // If element was found if ($index != -1) echo 'Element found at index '.$index; else echo 'Element not found.'; return 0; #This code is contributed by Susobhan Akhuli ?> 

// C++ program to implement interpolation search by using iteration approach #include   using namespace std;   int interpolationSearch(int arr[] int n int x) {  // Find indexes of two corners  int low = 0 high = (n - 1);  // Since array is sorted an element present  // in array must be in range defined by corner  while (low <= high && x >= arr[low] && x <= arr[high])  {  if (low == high)  {if (arr[low] == x) return low;  return -1;  }  // Probing the position with keeping  // uniform distribution in mind.  int pos = low + (((double)(high - low) /  (arr[high] - arr[low])) * (x - arr[low]));    // Condition of target found  if (arr[pos] == x)  return pos;  // If x is larger x is in upper part  if (arr[pos] < x)  low = pos + 1;  // If x is smaller x is in the lower part  else  high = pos - 1;  }  return -1; }   // Main function int main() {  // Array of items on whighch 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 n x);    // If element was found  if (index != -1)  cout << 'Element found at index ' << index;  else  cout << 'Element not found.';  return 0; }  //this code contributed by Ajay Singh 

// 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;  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.');  } } 

# Python equivalent of above C++ code  # Python program to implement interpolation search by using iteration approach def interpolationSearch(arr n x): # Find indexes of two corners  low = 0 high = (n - 1) # Since array is sorted an element present  # in array must be in range defined by corner  while low <= high and x >= arr[low] and x <= arr[high]: if low == high: if arr[low] == x: return low; return -1; # Probing the position with keeping  # uniform distribution in mind.  pos = int(low + (((float(high - low)/( arr[high] - arr[low])) * (x - arr[low])))) # Condition of target found  if arr[pos] == x: return pos # If x is larger x is in upper part  if arr[pos] < x: low = pos + 1; # If x is smaller x is in lower part  else: high = pos - 1; return -1 # Main function if __name__ == '__main__': # Array of items on whighch search will  # be conducted. arr = [10 12 13 16 18 19 20 21 22 23 24 33 35 42 47] n = len(arr) x = 18 # Element to be searched index = interpolationSearch(arr n x) # If element was found if index != -1: print ('Element found at index'index) else: print ('Element not found') 

// C# program to implement interpolation search by using // iteration approach using System; class Program {  // Interpolation Search function  static int InterpolationSearch(int[] arr int n int x)  {  int low = 0;  int high = n - 1;    while (low <= high && x >= arr[low] && x <= arr[high])   {  if (low == high)   {  if (arr[low] == x)   return low;   return -1;   }    int pos = low + (int)(((float)(high - low) / (arr[high] - arr[low])) * (x - arr[low]));    if (arr[pos] == x)   return pos;     if (arr[pos] < x)   low = pos + 1;     else   high = pos - 1;   }    return -1;  }    // Main function  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 n x);    if (index != -1)   Console.WriteLine('Element found at index ' + index);  else   Console.WriteLine('Element not found');  } } // This code is contributed by Susobhan Akhuli 

// JavaScript program to implement interpolation search by using iteration approach function interpolationSearch(arr n x) { // Find indexes of two corners let low = 0; let high = n - 1; // Since array is sorted an element present // in array must be in range defined by corner while (low <= high && x >= arr[low] && x <= arr[high]) {  if (low == high) {  if (arr[low] == x) {  return low;  }  return -1;  }  // Probing the position with keeping  // uniform distribution in mind.  let pos = Math.floor(low + (((high - low) / (arr[high] - arr[low])) * (x - arr[low])));  // Condition of target found  if (arr[pos] == x) {  return pos;  }  // If x is larger x is in upper part  if (arr[pos] < x) {  low = pos + 1;  }  // If x is smaller x is in lower part  else {  high = pos - 1;  } } return -1; } // Main function let arr = [10 12 13 16 18 19 20 21 22 23 24 33 35 42 47]; let n = arr.length; let x = 18; // Element to be searched let index = interpolationSearch(arr n x); // If element was found if (index != -1) { console.log('Element found at index' index); } else { console.log('Element not found'); }