Interpolation Search is an advanced searching algorithm that works similarly to Binary Search but uses a more intelligent approach to guess where the target might be. Instead of always checking the middle of a sorted array, Interpolation Search estimates the position based on the value of the target relative to the first and last elements. This makes it particularly efficient for uniformly distributed datasets, where values are spread evenly.
with hands-on learning.
get the skills and confidence to land your next move.
Learning Interpolation Search is useful because it demonstrates how algorithms can be optimized by using the properties of the data. While Binary Search divides the array evenly, Interpolation Search predicts the likely position of the target, which can reduce the number of comparisons in certain cases. For beginners in TypeScript, implementing Interpolation Search provides practice with formulas, loops, recursion, and working with sorted data.
Program 1: Iterative Interpolation Search
This program demonstrates the classic iterative approach to Interpolation Search. It calculates the estimated position of the target and adjusts the search range accordingly.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let data: number[] = [10, 20, 30, 40, 50, 60, 70];
let targetValue: number = 40;
console.log("Element found at index:", interpolationSearch(data, targetValue));This program estimates the position of the target using the formula based on proportional distance. Beginners can understand it as a “smart guess” that improves efficiency for evenly spaced values.
Program 2: Recursive Interpolation Search
Recursion can also be used to implement Interpolation Search, allowing the algorithm to divide the search space naturally.
function interpolationSearchRecursive(arr: number[], target: number, low: number = 0, high: number = arr.length - 1): number {
if (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) return interpolationSearchRecursive(arr, target, pos + 1, high);
else return interpolationSearchRecursive(arr, target, low, pos - 1);
}
return -1;
}
let numbers: number[] = [5, 15, 25, 35, 45, 55];
let searchValue: number = 35;
console.log("Element found at index:", interpolationSearchRecursive(numbers, searchValue));This recursive approach shows beginners how the search space can shrink naturally while making smart guesses based on the values. Recursion also helps in visualizing the algorithm’s logic clearly.
Program 3: Interpolation Search for Negative Numbers
Interpolation Search works with negative numbers as long as the array is sorted.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let negatives: number[] = [-50, -40, -30, -20, -10, 0, 10];
let targetNegative: number = -20;
console.log("Element found at index:", interpolationSearch(negatives, targetNegative));Beginners can see that the algorithm does not require special handling for negative numbers because the formula works with all numerical values.
Program 4: Interpolation Search for Floating Point Numbers
This program demonstrates that Interpolation Search can also handle decimals in a sorted array.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let decimals: number[] = [0.5, 1.0, 1.5, 2.0, 2.5, 3.0];
let targetDecimal: number = 2.0;
console.log("Element found at index:", interpolationSearch(decimals, targetDecimal));This example reinforces the idea that Interpolation Search is versatile, working with both integers and floating point numbers in uniformly distributed datasets.
Program 5: Interpolation Search for Large Arrays
Interpolation Search is especially efficient for large, evenly distributed datasets.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let largeArray: number[] = Array.from({length: 1000}, (_, i) => i * 2); // 0, 2, 4, ..., 1998
let targetLarge: number = 1500;
console.log("Element found at index:", interpolationSearch(largeArray, targetLarge));Even with a thousand elements, the algorithm quickly finds the target by estimating its position rather than checking sequentially. Beginners can appreciate how this makes Interpolation Search faster than Linear Search in certain scenarios.
Program 6: Interpolation Search with Duplicate Values
This program demonstrates that Interpolation Search can find any occurrence of a target in an array with repeated values.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let duplicates: number[] = [10, 20, 20, 30, 40, 40, 50];
let targetDuplicate: number = 40;
console.log("Element found at index:", interpolationSearch(duplicates, targetDuplicate));Although it may return any occurrence of the target, beginners can see that the algorithm efficiently finds the target without scanning the entire array.
Program 7: Interpolation Search for Random Uniform Data
This program shows Interpolation Search applied to a uniformly distributed dataset.
function interpolationSearch(arr: number[], target: number): number {
let low = 0;
let high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
let pos = low + Math.floor(((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] === target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
let uniformData: number[] = [5, 10, 15, 20, 25, 30, 35];
let targetUniform: number = 25;
console.log("Element found at index:", interpolationSearch(uniformData, targetUniform));Beginners can observe that Interpolation Search is most effective when the data is evenly spaced, as the formula predicts positions accurately.
Frequently Asked Questions (FAQ)
Interpolation Search can raise common questions for beginners:
Q1. Can Interpolation Search work on unsorted arrays?
No, the array must be sorted for the position formula to be valid.
Q2. Is Interpolation Search faster than Binary Search?
It can be faster for uniformly distributed data because it predicts positions instead of checking the middle every time.
Q3. Can Interpolation Search handle negative numbers and decimals?
Yes, it works with any numerical values as long as the array is sorted.
Q4. Does Interpolation Search always return the first occurrence of a duplicate?
No, it may return any occurrence of the target. Special handling is required to find the first occurrence.
Q5. When is Interpolation Search most efficient?
It is most efficient on large, uniformly distributed datasets where the target value can be predicted accurately.
Conclusion
Interpolation Search is an advanced searching algorithm that improves upon Binary Search by predicting the likely position of the target. In this article, we explored several TypeScript programs implementing Interpolation Search using loops, recursion, negative numbers, decimals, duplicates, and large arrays. Each example showed how the algorithm estimates positions to reduce comparisons and improve efficiency.
By practicing these examples, beginners can gain a deeper understanding of search algorithms, the power of formulas for predictions, and how data distribution affects performance. Mastering Interpolation Search is a step toward becoming confident in applying more efficient search techniques in TypeScript and real-world programming scenarios.
