An algorithm for searching in a sorted array that estimates the position of the target element based on the values at the current bounds, similar to how a human searches a dictionary.
Parameters
15
Visualization
Step: 0
Enter a target and click Step or Auto-Run.
Algorithm Insight
Predicts the location of the target mathematically:
3.If target is larger, low = pos + 1. If smaller, high = pos - 1.
Efficiency
Time (Avg)O(log log N)
Time (Worst)O(N)
Deconstructing Interpolation Search
The "phone book" search algorithm that makes intelligent guesses to find data faster.
Quick Context: What is Interpolation Search?
Interpolation Search is an algorithm for finding a key in a sorted and uniformly distributed array. While Binary Search always checks the middle element, Interpolation Search makes an intelligent guess. Think about searching for a name like "Smith" in a phone book. You wouldn't open to the middle; you'd open to the 'S' section, far down the book. Interpolation Search does the same, estimating where the target is likely to be based on the values at the ends of the search area.
The Core Idea: The Interpolation Formula
Instead of blindly dividing the search space in half, the algorithm predicts the location of the target value using a formula. This formula calculates a "probe" position based on how far the target value is between the `low` and `high` values of the current search range.
`low` and `high`: These are the indices of the current search range.
`arr[low]` and `arr[high]`: These are the values at the boundaries of the search range.
`target`: The value you are looking for.
The formula estimates the target's position proportionally. If the target is close to `arr[high]`, the probe position `pos` will be close to `high`. If it's close to `arr[low]`, `pos` will be close to `low`.
Guided Experiments with the Visualizer
Set a Low Target: Start with the default array. Set the "Search Target" to a low number that's in the array (e.g., 11). Click "Next Step". Notice the "Probe" (yellow bar) jumps to an index near the beginning. The algorithm predicted the target would be in the lower part of the array.
Set a High Target: Now, reset and set the target to a high number (e.g., 89). Click "Next Step". This time, the probe jumps to an index near the end. This is the "intelligent guess" in action.
Observe the Shrinking Range: Click "Next Step" again. Based on the comparison, the algorithm dramatically shrinks the search range by updating the `low` or `high` pointers. The discarded part of the array is faded out.
Auto-Run: Click "Auto-Run" and watch the process. For a uniformly distributed array, you'll see that Interpolation Search often finds the target in far fewer steps than a Binary Search would, as its guesses are much more accurate.
When It's Not Ideal: If the data is not uniformly distributed (e.g., it increases exponentially), the guesses become less accurate, and the performance can degrade to O(n) in the worst case, which is worse than Binary Search's guarantee.
Performance and Ideal Conditions
Time Complexity:
Best and Average Case: O(log(log n)) — This is significantly faster than Binary Search's O(log n), but it relies on the data being uniformly distributed.
Worst Case: O(n) — Occurs with non-uniform data (e.g., exponential growth), where the probes repeatedly land near the ends of the search space.
Space Complexity: O(1) — It is an in-place algorithm.
Ideal Conditions: Works best on large, sorted arrays where the values are evenly spread out (e.g., numbers 1 to 1,000,000 with few gaps).
Key Takeaways
Smarter Than Binary Search: It uses the data's values to make a better guess about where the target might be.
Data Distribution is Key: Its incredible speed is only realized when the data is uniformly distributed.
No "Blind" Probing: Unlike Binary Search, it doesn't always check the middle, making it feel more human-like in its approach.
A Trade-off: You trade the guaranteed O(log n) performance of Binary Search for a potentially much faster O(log(log n)) average time, at the risk of a slow O(n) worst case.
Cheat sheet
Interpolation Search
An algorithm for searching in a sorted array that estimates the position of the target element based on the values at the current bounds, similar to how a human searches a dictionary.