AlgoThrive
← All searching algorithms

Interpolation Search

CheckingRuled outFound

array

target = 12
2
4
6
8
10
12
14
16
0
1
2
3
4
5
6
7

pseudocode

interpolationSearch(a, target)
  lo = 0; hi = n - 1
  while lo <= hi and target >= a[lo] and target <= a[hi]
    pos = lo + ((target - a[lo]) * (hi - lo)) / (a[hi] - a[lo])
    if a[pos] == target return pos
    if a[pos] < target then lo = pos + 1
    else hi = pos - 1
  return -1

Frame 1 / 3

Looking for 12 in range [0…7]

estimate index using value distribution

4

Pick a value that is in the array — or one that isn't, to watch the search fail.

3–16 integers between 1 and 20 — the array is sorted for you, because binary search needs ordered data.