Introduction
Hi Everyone,
In this Article, we will learn about the working of Interpolation Search. Interpolation Search is an advanced searching algorithm that improves upon binary search for uniformly distributed, sorted arrays. While binary search always divides the search space in half, interpolation search makes intelligent guesses about where the target element might be located based on the value being searched.
Syntax
pos = low + ((target - arr[low]) / (arr[high] - arr[low])) * (high - low);
This Syntax assumes that the elements are uniformly distributed. The position calculation is based on the proportion of where the target value falls within the range of values between the current low and high indexes.
Steps
- Calculate the probable position using the interpolation formula
- If the element at the calculated position matches the target, return the position
- If the target is smaller than the element at the calculated position, search the left subarray
- If the target is larger, search the right subarray
- Repeat until the element is found or the search space is exhausted
Code Example
package com.loki.dsa.sorting.blog;
import java.util.Arrays;
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
// Continue searching while the target is within the range
while (low <= high && target >= arr[low] && target <= arr[high]) {
// If there's only one element left
if (low == high) {
return arr[low] == target ? low : -1;
}
// Calculate the probable position using interpolation formula
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
// Ensure pos is within bounds (safety check)
if (pos < low || pos > high) {
break;
}
// If element found at calculated position
if (arr[pos] == target) {
return pos;
}
// If target is smaller, search left subarray
if (arr[pos] > target) {
high = pos - 1;
} else {
// If target is larger, search right subarray
low = pos + 1;
}
}
return -1; // Element not found
}
/**
* Recursive implementation of interpolation search
*/
public static int interpolationSearchRecursive(int[] arr, int low, int high, int target) {
// Base cases
if (low > high || target < arr[low] || target > arr[high]) {
return -1;
}
if (low == high) {
return arr[low] == target ? low : -1;
}
// Calculate probable position
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
// Safety check for position bounds
if (pos < low || pos > high) {
return -1;
}
// If element found
if (arr[pos] == target) {
return pos;
}
// Recursive calls for subarrays
if (arr[pos] > target) {
return interpolationSearchRecursive(arr, low, pos - 1, target);
} else {
return interpolationSearchRecursive(arr, pos + 1, high, target);
}
}
public static void main(String[] args) {
// Test with uniformly distributed array
int[] uniformArray = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
System.out.println("Array: " + Arrays.toString(uniformArray));
int target = 70;
int result = interpolationSearch(uniformArray, target);
if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {
System.out.println("Element " + target + " not found");
}
// Test with non-uniform array
int[] nonUniformArray = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
System.out.println("\nNon-uniform array: " + Arrays.toString(nonUniformArray));
target = 64;
result = interpolationSearch(nonUniformArray, target);
if (result != -1) {
System.out.println("Element " + target + " found at index " + result);
} else {
System.out.println("Element " + target + " not found");
}
// Test recursive implementation
target = 32;
result = interpolationSearchRecursive(nonUniformArray, 0, nonUniformArray.length - 1, target);
System.out.println("Recursive search for " + target + ": " +
(result != -1 ? "found at index " + result : "not found"));
}
}
Join the conversation! Your thoughts help the community grow.