Interpolation Search
Improved Binary Search for uniformly distributed data. Probes position based on value.
Enter target and search
1function interpolationSearch(arr, x):
2 lo = 0, hi = n - 1
3 while lo <= hi and x >= arr[lo] and x <= arr[hi]:
4 if lo == hi:
5 return arr[lo] == x ? lo : -1
6
7 pos = lo + ((hi-lo)/(arr[hi]-arr[lo]) * (x-arr[lo]))
8
9 if arr[pos] == x: return pos
10 if arr[pos] < x: lo = pos + 1
11 else: hi = pos - 1
12 return -1
Complexity
TimeO(log(log n))
WorstO(n)