Computing mid in Interpolation Search?

Question

I came to know that Interpolation Search is a modification of Binary Search where in binary search the input is divided into two equal halves in each iteration by computing

mid = (low + high) / 2

and in Interpolation search the mid is computed as

mid = low + (key - arr[low]) * ((high - low) / (arr[high] - arr[low]))

Now I need to understand this formula of calculating mid in interpolation search.

Ref: https://en.wikipedia.org/wiki/Interpolation_search#Sample_implementation

Answer 1

You can think of array arr as a function f that acts on index and return a value, which is monotone (because array is sorted). So you have your initial data f(low) = m and f(high) = M. Now you can interpolate your function f with a straight line, which is quite reasonable to do because your f is monotone and you have only 2 points. So your interpolation should be line (linear function) that pass throw points (low, m) and (high, M). This is it's equation

(y - f(low))/(f(high) - f(low)) = (x - low)/(high - low)

So y here is the element of search space and x is from domain (x is index of array). So if your function f would be the same as it's interpolation, then index of your key would be:

x = low + (high - low)*(key - f(low))/(f(high) - f(low))

So, assuming that your function f is close to it's interpolation, you should just check the value f at x to see if it is the goal. Otherwise you just shrink your interpolation interval.