Probe by value, not by the middle — guess where the target should be assuming values are evenly spread. O(log log n) on uniform data.
Interpolation search improves on binary search with one insight: if a sorted list's values are *evenly spread*, you can guess where the target should be instead of always splitting the middle. Hunting for 'Smith' in a phone book, you don't open to the center — you open near the back. Hunting for 95 in a 1…100 list, you probe near the far end. That informed guess, not a blind halving, is the whole idea.
Binary search always picks the midpoint. Interpolation search instead computes how far the target's value sits between the low and high values, and probes that fraction of the way through the index window:
pos = lo + ((target - arr[lo]) * (hi - lo))
/ (arr[hi] - arr[lo])
// target near arr[lo] -> pos near lo (probe left)
// target near arr[hi] -> pos near hi (probe right)
// target halfway value -> pos near mid (like binary search)lo and hi, as in binary search.pos from the formula above — proportional to the target's *value*, not the window's center.arr[pos] equals the target → found.arr[pos] is less → the answer is to the right, so lo = pos + 1.arr[pos] is greater → the answer is to the left, so hi = pos - 1.log log n probes: a list of a billion uniform values is found in around five.