Interpolation search

O(log log n) avg

Interpolation search improves on binary search for uniformly distributed sorted data: instead of always probing the middle, it estimates the position proportionally to where the target falls between the lo and hi values. On uniform data it can reach O(log log n); on skewed data it degrades toward O(n).

Array
Edit the input and press Play

How it works

  1. Estimate the probe position by interpolating the target between the range's lowest and highest values.
  2. Compare the value there with the target.
  3. If smaller, search the right part; if larger, the left part.
  4. Repeat until found or the range no longer brackets the target.

Pseudocode

1interpolationSearch(a, target):     # O(log log n) avg — a is sorted2  lo ← 0; hi ← n-13  while lo ≤ hi and a[lo] ≤ target ≤ a[hi]:4    pos ← lo + (target-a[lo])*(hi-lo) / (a[hi]-a[lo])5    if a[pos] = target: return pos6    if a[pos] < target: lo ← pos+17    else: hi ← pos-18  return -1