Interpolation search is an improvement over binary search for uniformly distributed sorted arrays. Instead of always checking the middle element, it estimates where the target is likely to be based on its value relative to the endpoints — like how you'd look up a word in a dictionary: 'Z' words are near the back, not the middle.
On uniformly distributed data, this gives an average of O(log log n) comparisons — significantly better than binary search's O(log n). For one million elements: binary search needs ~20 comparisons, interpolation search needs ~4. The catch: it requires uniform distribution to perform well.
Mathematical probe position The probe formula is: lo + ((target − arr[lo]) × (hi − lo)) / (arr[hi] − arr[lo]). This estimates how far through the range the target should be, based on value proportionality. Points directly to the likely position.
O(log log n) on uniform data With evenly spaced values, each probe is so accurate that the search space shrinks exponentially faster than binary search's halving. For n=1,000,000 you need only about 4 comparisons on average.
If values are clustered at one end (e.g. exponential distribution), the formula gives a wildly inaccurate probe, and the algorithm falls back to O(n) behaviour. Always check your data distribution before using it.
Requires sorted numeric keys The formula relies on numeric value comparison between the target and endpoint values. It works on integers and floats, but not on strings or objects without a numeric mapping.
TIPUse the default uniformly-spaced array [10,20,30,40,50,60,70,80] and search for 50. The probe formula jumps almost exactly to index 4 on the first try — this is O(log log n) in action. Then try a value near the edges like 10 or 80 and watch how the formula places the probe near the end of the range.