In this post we’ll see how to write Interpolation search program in Java. Interpolation search is a variation of Binary search, meaning it is also a divide and conquer algorithm how it differs is that rather than dividing the input array into two equal parts it tries to divide the array in such a way that the position is nearer to the searched element.
How does Interpolation search work
One of the prerequisite for the Interpolation search is that the input array should be sorted and the values are uniformly distributed.
Interpolation search takes into account the lowest and highest elements in the array as well as length of the array and tries to estimate the position of the searched element. It works on the principle that the searched element is likely to be located near the end of the array if the searched element is close to the highest element in the array and it is likely to be located near the start of the array if the searched element is close to the lowest element in the array.
Interpolation search uses the following formula to calculate the position to be compared with the searched element.
position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] – arr[start]))
In each iteration searched element is compared with the element at the calculated position and start and end are adjusted based upon whether the searched element is greater than or less than the calculated position.
Interpolation search Java Program
public class InterpolationSearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73};
Arrays.sort(arr);
System.out.println("sorted array- " + Arrays.toString(arr));
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = interpolationSearch(arr, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
sc.close();
}
private static int interpolationSearch(int[] arr, int searchElement){
int start = 0;
int end = arr.length - 1;
int position;
while ((arr[end] != arr[start]) && (searchElement >= arr[start]) && (searchElement <= arr[end])) {
position = start + ((searchElement - arr[start]) * (end - start) / (arr[end] - arr[start]));
// Nearer to the highest element
if (arr[position] < searchElement)
start = position + 1;
// Nearer to the lowest element
else if (searchElement < arr[position])
end = position - 1;
else
return position;
}
if (searchElement == arr[start])
return start ;
else
return -1;
}
}
Output for few of the searches-
sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73] Enter value to search: 55 Searched item 55 found at index 6 sorted array- [3, 4, 10, 12, 23, 34, 55, 68, 73] Enter value to search: 23 Searched item 23 found at index 4
Interpolation search Performance
Average case time complexity of Interpolation search is O(log(log(n))) if the elements are uniformly distributed. In worst case time complexity can be O(n).
Space complexity of Interpolation search is O(1) as no auxiliary space is required.
That's all for this topic Interpolation Search Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-