在这里,我试图在Python(3.6.1)中实现插值搜索。我的逻辑似乎是正确的,但输出总是给我False,除非我将列表的第一个索引作为搜索键。代码如下:
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))
阅读:How-to-debug-small-programs/
我在你的时间设置了一个断点,并努力查看你的例子的值。
# 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。
插值搜索是一种用于搜索已按数值排序的索引数组中的给定键的算法
然后我查看了你的输入:
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...