Interpolation Search Algorithm
Interpolation search algorithm is an advanced searching technique that works specifically on uniformly distributed sorted arrays or lists. It is an improvement over the binary search algorithm, which eliminates half of the remaining items in each iteration. The main idea behind the interpolation search is to estimate the position of the target value in the array, based on the values of the first and last elements, and the target value itself. This estimation is done using a linear interpolation formula, which calculates the probable position of the target value, allowing the search to potentially skip over a large number of irrelevant elements, thus significantly reducing the time complexity of the search.
In the interpolation search algorithm, the initial position is calculated using the formula: position = low + ((target - array[low]) * (high - low) / (array[high] - array[low])). Here, low and high represent the indices of the first and last elements of the current search range, while target is the value to be searched. If the calculated position is within the search range and the value at the calculated position is equal to the target value, the search is successful, and the index of the target value is returned. If the value at the calculated position is less than the target value, the search range is updated to start from the next element after the calculated position, i.e., low = position + 1. Conversely, if the value at the calculated position is greater than the target value, the search range is updated to end at the element before the calculated position, i.e., high = position - 1. The algorithm repeats this process until the target value is found or the search range becomes empty, indicating that the target value is not present in the array. The interpolation search algorithm boasts an average case time complexity of O(log log n) for uniformly distributed data, which is better than the binary search's O(log n) complexity. However, in the worst case, the interpolation search can degrade to O(n) complexity, which is slower than the binary search.
package Searches;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import static java.lang.String.format;
/**
* Interpolation search algorithm implementation
* <p>
* Worst-case performance O(n)
* Best-case performance O(1)
* Average performance O(log(log(n))) if the elements are uniformly distributed if not O(n)
* Worst-case space complexity O(1)
*
* @author Podshivalov Nikita (https://github.com/nikitap492)
*/
class InterpolationSearch {
/**
* @param array is a sorted array
* @param key is a value what shoulb be found in the array
* @return an index if the array contains the key unless -1
*/
public int find(int array[], int key) {
// Find indexes of two corners
int start = 0, end = (array.length - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (start <= end && key >= array[start] && key <= array[end]) {
// Probing the position with keeping
// uniform distribution in mind.
int pos = start + (((end - start) / (array[end] - array[start])) * (key - array[start]));
// Condition of target found
if (array[pos] == key)
return pos;
// If key is larger, key is in upper part
if (array[pos] < key)
start = pos + 1;
// If key is smaller, x is in lower part
else
end = pos - 1;
}
return -1;
}
// Driver method
public static void main(String[] args) {
Random r = new Random();
int size = 100;
int maxElement = 100000;
int[] integers = IntStream.generate(() -> r.nextInt(maxElement)).limit(size).sorted().toArray();
//the element that should be found
Integer shouldBeFound = integers[r.nextInt(size - 1)];
InterpolationSearch search = new InterpolationSearch();
int atIndex = search.find(integers, shouldBeFound);
System.out.println(String.format("Should be found: %d. Found %d at index %d. An array length %d"
, shouldBeFound, integers[atIndex], atIndex, size));
int toCheck = Arrays.binarySearch(integers, shouldBeFound);
System.out.println(format("Found by system method at an index: %d. Is equal: %b", toCheck, toCheck == atIndex));
}
}
