Loading…
Loading…
Like binary search, but estimates the probe position from the target's value — near O(log log n) on uniformly distributed data.
Estimate position of 53 by interpolation.
Tip: click any bar to make it the target.
1int interpolationSearch(int[] a, int target) {2 int lo = 0, hi = a.length - 1;3 while (lo <= hi && target >= a[lo] && target <= a[hi]) {4 int pos = lo + (target-a[lo])*(hi-lo)/(a[hi]-a[lo]);5 if (a[pos] == target) return pos;6 else if (a[pos] < target) lo = pos + 1;7 else hi = pos - 1;8 }9 return -1;10}