为何插值搜索计算位置与线性搜索一致？代码是否有误？

问题出在插值位置计算的优先级与顺序错误，导致公式完全失效，最终退化为线性遍历。

原代码中的pos计算逻辑：

pos = lo + ((hi - lo) // (ar[hi] - ar[lo]) * (x - ar[lo]))

在Python中，整数除法//和乘法*优先级相同，运算顺序为从左到右。以第一次调用为例：

• hi-lo = 14，ar[hi]-ar[lo] = 47-10=37，14//37结果为0
• 0乘以x-ar[lo] = 18-10=8，结果仍为0
• 最终pos=0+0=0

每次递归时，(hi-lo)//(ar[hi]-ar[lo])的结果都是0（数组元素间隔小，区间长度除以值范围的商小于1，整数除法后取整为0），导致pos始终等于当前lo。又因为ar[pos]<x，递归调用pos+1，最终变成了逐个递增的线性搜索。

正确的插值搜索公式应先计算分子部分(x-ar[lo])*(hi-lo)，再除以分母(ar[hi]-ar[lo])，修正后的代码：

def interpolation_search(ar:list, lo:int, hi:int, x:int):                                
    if (lo <= hi and x >= ar[lo] and x <= ar[hi]):                                       
        # 调整计算顺序，先算乘法再做整数除法
        pos = lo + ((x - ar[lo]) * (hi - lo)) // (ar[hi] - ar[lo])                       
                                                                                           
        print(pos)                                                                       
                                                                                             
        if ar[pos] == x:                                                                 
            return pos                                                                   
                                                                                           
        if ar[pos] < x:                                                                  
            return interpolation_search(ar, pos + 1, hi, x)                              
                                                                                             
        if ar[pos] > x:                                                                  
            return interpolation_search(ar, lo, pos - 1, x)                              
                                                                                             
    return -1 
    
if __name__ == '__main__':                                                               
    v = 18                                                                                                                                                 
    ar = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]                                                           
    assert(interpolation_search(ar, 0, len(ar)-1, v) == 4) 

修正后运行代码，print(pos)会直接输出4，一次定位到目标值，符合插值搜索的预期。

内容的提问来源于stack exchange，提问作者user23145140