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

Question

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

该算法似乎确实有效，它打印我正在搜索的元素的索引，或者当元素不在列表中时显示“未找到值”。但是 while 循环永远不会终止，即使我在找到/找不到值后设置 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 变量对于 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")