Code:
import java.util.Scanner;
/** Class InterpolationSearch **/
public class InterpolationSearch
{
/** interpolationSearch function **/
public static int interpolationSearch(int[] sortedArray, int toFind)
{
int low = 0;
int high = sortedArray.length - 1;
int mid;
while (sortedArray[low] <= toFind && sortedArray[high] >= toFind)
{
if (sortedArray[high] - sortedArray[low] == 0)
return (low + high)/2;
/** out of range is possible here **/
mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]);
if (sortedArray[mid] < toFind)
low = mid + 1;
else if (sortedArray[mid] > toFind)
high = mid - 1;
else
return mid;
}
if (sortedArray[low] == toFind)
return low;
/** not found **/
else
return -1;
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Interpolation Search Test\n");
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create integer array on n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println("\nEnter "+ n +" sorted integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
System.out.println("\nEnter element to search for : ");
int key = scan.nextInt();
int result = interpolationSearch(arr, key);
if (result == -1)
System.out.println("\n"+ key +" element not found");
else
System.out.println("\n"+ key +" elemnt found at position "+ result);
}
}
Output:
Enter number of integer elements
10
Enter 10 sorted integer elements
12 24 36 48 60 72 84 96 108 120
Enter element to search for :
24
24 elemnt found at position 1
More Java Programs:
