Python跳转搜索算法不返回一个numb

Question

我正在尝试实现一个跳转搜索算法。然而，在下面的这个例子中，我找不到72这个数字，尽管它在我定义的列表中很清楚。这是代码，有人能给我解释一下为什么剩下的数字可以返回，而不是列表中索引0处的72吗？你知道吗

def jumpSearch(list, number, constant) :
    i = 0
    counter = 0
    while (list[i] < number and i + constant < len(list) and list[i + constant] < number) :
        i = i + constant

    for j in range (i, i + constant, 1) :
        if (list[j] == number) :
            return list[j]
    return None

mylist = [72, 56, 93, 8, 22, 41, 88, 23, 60]
mylist.sort()
print(jumpSearch(mylist, 72, 3))

我在网上看到过其他的例子，但是，我真的很想测试一下自己的能力，从零开始编写代码和逻辑，以便得到结果。你知道吗

因此，我对跳转搜索的初步理解使我无法知道这是否是跳转搜索的“正确”方法。对代码的任何评估或改进，甚至是编写跳转搜索的“最佳和正确”方法的示例，对我的学习都是有价值的！你知道吗

Answer 1

如果您查看while循环，您将看到当list[i + constant]不再小于72时会发生什么：

while (... list[i + constant] < number):

当list[i + constant]较小时递增，而不是相等或较大时递增。你知道吗

所以我们知道这个值在list[i]和list[i + constant]之间。但是，range()产生的数字独占结束值。从^{} documentation：

For a positive step, the contents of a range r are determined by the formula r[i] = start + step*i where i >= 0and r[i] < stop.

（我的粗体强调）。你知道吗

所以你有一个错误。由range()产生的最后一个值是i + constant - 1，而72则位于i + constant。你知道吗

您需要在结束值中添加一个，然后在range(i, i + constant + 1)中搜索：

for j in range (i, i + constant + 1):

Answer 2

我为您的函数添加了一些调试输出，以便您可以看到发生了什么：

def jumpSearch(mylist, number, constant):
    i = 0
    counter = 0

    while (mylist[i] < number 
          and i + constant < len(mylist)
          and mylist[i + constant] < number):

        format_str= "In while:\n\t mylist[{}]={},number={},i+constant={},len(mylist)={},mylist[i+constant]={}"

        print( 
            format_str.format(
                i,
                mylist[i], 
                number,
                constant,
                len(mylist),
                mylist[i+constant]
            )
        )


        i = i + constant
        print("\t i={},mylist[{}+3]={},number={}".format(i,i,mylist[i+3],number))


    for j in range (i, i + constant, 1):

        f_string =  "In for:\n\t j={},i={},i+constant={},mylist[{}]={},number={}"
        print( f_string.format(j, i, i+constant, j, mylist[j], number))

        if (mylist[j] == number) :
            return mylist[j]

    return None

mylist = [72, 56, 93, 8, 22, 41, 88, 23, 60]
mylist.sort() #=> [8, 22, 23, 41, 56, 60, 72, 88, 93]
print(jumpSearch(mylist, 72, 3))

 output: 
In while:
     mylist[0]=8,number=72,i+constant=3,len(mylist)=9,mylist[i+constant]=41
     i=3,mylist[3+3]=72,number=72
In for:
     j=3,i=3,i+constant=6,mylist[3]=41,number=72
In for:
     j=4,i=3,i+constant=6,mylist[4]=56,number=72
In for:
     j=5,i=3,i+constant=6,mylist[5]=60,number=72
None

可以看到while循环只执行一次。while循环的第二行输出显示mylist[3+3]等于number，while循环的下一次迭代测试mylist[6] < number，这是false。因此，执行跳转到for循环，并且输出显示for循环从未找到等于72的mylist[j]

Answer 3

72的索引正好是其中一个步骤的（在您的例子中是6，步骤是3），您错过了它，因为您使用了<而不是<=符号。你知道吗

将list[i + constant] < number更改为list[i + constant] <= number。你知道吗