问插值搜索中的中间计算？

EN

您可以将数组arr看作是一个作用于索引并返回值的函数f，它是单调的(因为数组是排序的)。所以您有您的初始数据f(low) = m和f(high) = M。现在你可以用一条直线插值你的函数f，这是相当合理的，因为你的f是单调的，你只有2分。因此，你的插值应该是线(线性函数)，通过抛点，(low, m)和(high, M)。这是方程

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

所以这里的y是搜索空间的元素，x来自域(x是数组的索引)。因此，如果您的函数f与它的插值相同，那么key的索引将是：

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

因此，假设您的函数f接近它的插值，您应该检查x的值f，看看它是否是目标。否则，你只需缩小你的插值间隔。

扩展到@ answer -另一个有趣的答案

他提出的方程是基于插值公式 (一条线的方程)。

现在，将f()视为接受索引并返回其y轴值的函数，

y1 = f(low)
y2 = f(high)
x1 = low
x2 = high

(y - f(low)) = [(f(high) - f(low)) / (high - low)] * (x - low);

OR

x = low + [(high - low) * (y - f(low))] / (f(high) - f(low))

here: y = key
we are looking for position(value) of x.