WikiGalaxy
Interpolation Search
Understanding Interpolation Search
Concept Overview:
Interpolation search is an improved variant of binary search. This algorithm works on the principle of probing the position of the required value in a sorted array based on the value of the key being searched. It is particularly useful for uniformly distributed data.
public class InterpolationSearch {
public static int interpolationSearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
public static void main(String[] args) {
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
int x = 18;
int index = interpolationSearch(arr, x);
System.out.println("Element found at index: " + index);
}
}
Console Output:
Element found at index: 4
Example with Non-Uniform Distribution
Scenario:
Interpolation search performs poorly on non-uniformly distributed arrays. Let's see an example where the elements are clustered.
public class InterpolationSearchNonUniform {
public static int interpolationSearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
public static void main(String[] args) {
int arr[] = {1, 1, 1, 1, 1, 50, 100, 100, 100, 100, 100};
int x = 50;
int index = interpolationSearch(arr, x);
System.out.println("Element found at index: " + index);
}
}
Console Output:
Element found at index: 5
Handling Edge Cases
Edge Case Analysis:
When the element is not present or the array is empty, interpolation search must handle these cases gracefully.
public class InterpolationSearchEdgeCases {
public static int interpolationSearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
public static void main(String[] args) {
int arr[] = {};
int x = 18;
int index = interpolationSearch(arr, x);
System.out.println("Element found at index: " + index);
}
}
Console Output:
Element found at index: -1
Interpolation Search vs. Binary Search
Comparative Analysis:
While both interpolation and binary search are efficient search algorithms, their performance varies based on the data distribution. Interpolation search can outperform binary search on uniformly distributed arrays.
public class CompareSearches {
public static int binarySearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static int interpolationSearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
int pos = lo + ((x - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
public static void main(String[] args) {
int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
int x = 18;
int indexBinary = binarySearch(arr, x);
int indexInterpolation = interpolationSearch(arr, x);
System.out.println("Binary Search found at index: " + indexBinary);
System.out.println("Interpolation Search found at index: " + indexInterpolation);
}
}
Console Output:
Binary Search found at index: 4
Interpolation Search found at index: 4
Algorithm Complexity and Efficiency
Complexity Analysis:
The average-case time complexity of interpolation search is O(log log n), which is better than binary search's O(log n) for uniformly distributed data. However, in the worst case, it can degrade to O(n).
public class ComplexityAnalysis {
public static void main(String[] args) {
// Example code for complexity analysis
System.out.println("Interpolation Search Average Case: O(log log n)");
System.out.println("Interpolation Search Worst Case: O(n)");
System.out.println("Binary Search Average and Worst Case: O(log n)");
}
}
Console Output:
Interpolation Search Average Case: O(log log n)
Interpolation Search Worst Case: O(n)
Binary Search Average and Worst Case: O(log n)
