# Interpolation Search Program in Java

By | July 18, 2020

In this post, we will learn How to Implement the Interpolation search program in Java. Interpolation search is an algorithm which tries to improve the Binary search, I mean to say that it also follows the divide and conquer algorithm like binary search but how it differs is that rather than dividing the input array into two equal parts it basically tries to divide the array in such a way that the position is nearer to the searched element.

How Interpolation search for work?

One of the prerequisites of the Interpolation search is that the input array should be sorted and the values are uniformly distributed.
Interpolation search takes the lowest and highest elements into account in the array as well as the length of the array and tries to estimate the position of the searched element.
This algorithm usually 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.
Or 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 usually using the below formula to calculate the position to be compared with the searched element key.

position = start + ((searchKey – arr[start]) * (end – start) / (arr[end] – arr[start]))

In each iteration searching 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.

The average time complexity of Interpolation search is O(log(log(n))) if all elements are uniformly distributed. The worst-case time complexity can be O(n).
The space complexity of the Interpolation search is O(1) as Single auxiliary space is required to hold a position variable.

Below is the Complete Source code:

The Some input/output of this program:

Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
56
SearchKey 56 found at index 4

Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
80
SearchKey 80 found at index 7

Sorted array- [9, 24, 30, 45, 56, 67, 70, 80, 100]
Enter value to be searched:
34