Interpolation Search using Java...

Here is the code ....

public class InterpolationSearch {

 public static void main(String[] args) {

  // 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 };
  int valueToSearch = 33;
  int loc = searchElement(arr, valueToSearch, 0, arr.length - 1);

  if (loc != -1)
   System.out.print("Element appears at location : " + loc);
  else
   System.out.print("ELement not found");
 }

 // Recursive search : Interpolation search
 public static int searchElement(int[] arr, int valueTosearch, int low, int high) {

  if (high == low) {
   if (arr[high] == valueTosearch)
    return high;
   else
    return -1;
  } else {

   int pos = low + ((valueTosearch - arr[low]) * (high - low)) / (arr[high] - arr[low]);
   if (arr[pos] == valueTosearch)
    return pos;
   else if (arr[pos] > valueTosearch)
    return searchElement(arr, valueTosearch, low, pos - 1);
   else
    return searchElement(arr, valueTosearch, pos + 1, high);
  }
 }
}