Interpolation Search
Like opening a dictionary near the letter you need — estimate the position from the value itself. On uniformly distributed data it beats binary search with O(log log n) probes.
- Category
- Searching
- Time complexity
- O(log log n)
- Space complexity
- O(1)
Pseudocode
while lo ≤ hi and t in [a[lo], a[hi]] pos ← lo + (t−a[lo])(hi−lo)/(a[hi]−a[lo]) if a[pos] = t: return pos narrow to correct side
Reference implementation
# estimate position from value —
# assumes roughly uniform data
pos = lo + (t - a[lo]) * (hi - lo) \
// (a[hi] - a[lo])