插值搜索产生错误输出

Question

在这里，我尝试在Python（3.6.1）中实现插值搜索。我的逻辑似乎是正确的，但输出总是给我假，除非我把列表的第一个索引作为搜索键。 代码如下：

def NSearch(l,n,s):
    beg = 0
    end = (n-1)

    while (beg<=end) and (s>=l[beg]) and (s<=l[end]):
       p  = beg + int(((float(end - beg) / ( l[end] - l[beg])) * ( s - l[beg])))
       if (l[p]==s):
         return True
       if (l[p]<=s):
         beg = p + 1
       else:
         end = p - 1

    return False    

liost = [23, 76, 17, -87, 56]
#x = int(input())
x = 76
print(NSearch(liost,len(liost),x))

Answer 1

读取：How-to-debug-small-programs/

我在while上设置了一个断点，并仔细查看了示例的值。你知道吗

# while (beg<=end) and (s>=l[beg]) and (s<=l[end]):

while (0<=4) and (76>=23) and (76<=56):     # this is false, function does not enter while.

    # all code in while block never executed == irrelevant 

return False

然后我查了查interpolation search。你知道吗

Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values

然后我看了一下你的意见：

liost = [23, 76, 17, -87, 56]  # not ordered

并将其固定为：

x = 76
print(NSearch(sorted(liost),len(liost),x))

现在，如果找到它-添加了几个其他值来检查和瞧：工程。你知道吗

---

旁注：

print (x in liost) # prints True as well...