while循环不会在递归二分查找中停止

Question

我正在尝试在 python 中编写递归二进制搜索算法。但是，我将运行保持在一个无限的 while 循环中。恐怕这一定是我忽略的简单问题，但我无法在任何地方找到答案，大多数关于 while 循环不终止的问题确实使用其他条件而不是布尔值。

该算法似乎确实有效，它打印我正在搜索的元素的索引，或者当元素不在列表中时 "Value not found"。但是 while 循环永远不会终止，即使我在找到 found/not 值后设置 found = False。这是为什么？

def binarysearch(A, v, x, y):
found = True
while found:
    if x < y:
        h = (x+y) //2
        if A[h] < v:
            binarysearch(A, v, h+1, y)
        else:
            binarysearch(A, v, x, h)
    elif A[x] == v:
        found = False
        print("Element you are looking for is at index {}".format(x))
    else:
        found = False
        print("Value is not in array")

#Code to test the binarysearch algorithm
blist = []
for value in range(0,124):
    if value % 2 ==0:
        blist.append(value)

print(blist)
binarysearch(blist, 68, 0, len(blist)-1)

Answer 1

您使用 found = False 修改的 found 变量是 local 到 binarysearch 的特定递归调用的范围。它不是您尝试修改的 found 的实例，即递归树顶层的实例。因此，尽管当前作用域中的 while 循环会终止，但其上方作用域中的循环不会终止。

因为你已经有了一个基本完整的循环实现，而不是在它上面使用递归（这会导致范围相关的错误）你可以通过覆盖 x 和 y.

def binarysearch(A, v, x, y):
    found = True
    while found:
        if x < y:
            h = (x+y) //2
            if A[h] < v:
                x = h+1  // replaced
            else:
                y = h    // replaced
        elif A[x] == v:
            found = False
            print("Element you are looking for is at index {}".format(x))
        else:
            found = False
            print("Value is not in array")

Answer 2

我犯的错误是我在递归调用之上使用了 while 循环，这基本上是实现相同目的的两种方法。对于对使用递归而不是 while 循环来保持它的算法感兴趣的人运行，我在下面提供了它的工作版本。

def binarysearch(A, v, x, y):
    if x < y:
        h = (x+y) //2
        if A[h] < v:
            binarysearch(A, v, h+1, y)
        else:
            binarysearch(A, v, x, h)
    elif A[x] == v:
        print("Element you are looking for is at index {}".format(x))
    else:
        print("Value is not in array")

while循环不会在递归二分查找中停止

While loop will not stop in recursive binary search

python

algorithm

recursion

search

binary-search