No question Binary Search is one the greatest searching algorithms offering average runtime of O(log n), but still, there are circumstances when more efficient searching may be conducted.
Let’s describe one such example.
Consider two arrays:
- Array 1: 1 3 8 9 12 14 27 29 34 37
- Array 2: 10 20 30 40 50 60 70 80 90 100 110 120
Both of the preceding arrays are sorted in ascending order, however, if you look attentively Array 1 is not uniformly distributed, whereas Array 2 is uniformly distributed, that is, the items in Array 2 are arranged in regular intervals of equal size, in our example 10.
Now if we want to seek element 110 in Array 2, and we proceed by the standard binary search it will first choose the middle element and then reach 110 splitting the array into half each time.
What is Interpolation S?
Interpolation is a mathematical word, which is simply a procedure of estimating an intermediate value given some sequence of discrete data.
Understanding Interpolation Search
Interpolation search is an optimized variation of vanilla Binary Search, which is best suited for evenly distributed variables.
Almost the whole algorithm is identical to that of binary search, except picking the pivot point or probe which is picked dependent on the value being sought.
Interpolation Search Algorithm
- Find the probe using the formula
- Compare it with the data
- If the value is matched, return success
- If the value is smaller, choose the left sub-array and repeat steps from commencing
- If the value is bigger, choose the correct sub-array and repeat steps from commencing
- Repeat the preceding steps, if the element is discovered return success else return failure
The above approach works for items sorted in ascending order, for descending order if the value is bigger choose the left sub-array and vice versa.
Example
Consider the Array: 7 10 13 17 20 23 26 29 32
Element to search: 29
Now we will find the probe using the formula.
Initially
low=0, high=8
mid = 0 + (((8-0)/(32-7))*(29-7))
mid = 6
In this situation, we can see that the probe is right-biased since the needed value is on the right side of the array, similarly, if the value would have been on the left side of the array, the probe value would have been left-biased.
low=7, high=8
mid = 7 + (((8-7)/(32-29))*(29-29))
mid = 7
Here arr[mid] = 29 which is the needed element, so we converge to the result in only two passes.
Now let’s take a look at the Java code for Interpolation Search.
public class Searching {
boolean interpolationSearch(int arr[], int n) {
int lengthOfArray = arr.length;
int mid; // to store middle element
int low = 0;
int high = lengthOfArray - 1;
while (low <= high) {
mid = low + (((high - low) / (arr[high] - arr[low])) * (n - arr[low])); // Formula for finding the pivot point or probe
if (arr[mid] == n) {
return true;
} else if (arr[mid] < n) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
// Driver Code
public static void main(String args[]) {
Searching search = new Searching();
int arr[] = {
12,
16,
25,
37,
46,
55,
76,
86
};
if (search.interpolationSearch(arr, 76)) {
System.out.println("Element found !");
} else {
System.out.println("Element not found :( ");
}
}
}
Performance
Case |
Runtime |
Best |
O(1) |
Average |
O(log(log n)) |
Worst |
O(n) |
Auxiliary Space |
O(1) |
Interpolation search works best when the data are equally distributed and can converge to the solution in an average runtime of O(log (log n)).