python - 某些情况导致我的二分搜索进入无限循环

Question

当搜索不在列表中(但在列表范围内)的任何内容以及大于最大数字的任何内容时，我陷入了无限循环。例如，当在列表 [1,2,5,6] 中搜索 2 时，我的函数返回索引 1，这是正确的。如果我搜索 -1，它会返回 False，这是正确的。但是，如果我搜索 100 或 4，它就会陷入无限循环。

def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2

    print "Middle is: {}".format(a_list[mid])
    print a_list


    while len(a_list) > 0:
        if a_list[mid] == item:
            return mid
        elif a_list[mid] > item:
            return binary_search(a_list[:mid], item)
        elif a_list[mid] < item:
            return binary_search(a_list[mid:], item) + mid
        else:
            return False

a = binary_search([1, 2, 3, 4, 6, 7, 8], 5) # infinite loop
b = binary_search([1, 2, 3, 4, 6, 7, 8], 100) # infinite loop
c = binary_search([1, 2, 3, 4, 6, 7, 8], 8) # works correctly
d = binary_search([1, 2, 3, 4, 6, 7, 8], -2) # works correctly

Answer 1

这是我用来检查您的程序的代码。 pdb 允许您使用 s 一次执行一个命令，或使用 继续执行下一个 pdb.set_trace() c.你可以像这样使用它:

import pdb

def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2

    print "Middle is: {}".format(a_list[mid])
    print a_list


    print a_list, item
    pdb.set_trace()

    while len(a_list) > 0:
        if a_list[mid] == item:
            return mid
        elif a_list[mid] > item:
            return binary_search(a_list[:mid], item)
        elif a_list[mid] < item:
            return binary_search(a_list[mid:], item) + mid
        else:
            return False

现在，您的程序存在许多问题，最明显的是循环和递归的组合。这很少是正确的。我还要指出， while 循环中的每种情况都有一个 return 语句，因此 while 循环仅具有导致列表大小为 的搜索的效果>0 不返回任何内容。我怀疑这就是你想要的。

第二个问题是您尝试返回 mid 或 False 的索引。你想做的事情没有问题。问题在于将 binary_search(...) 添加到 mid 中。这样做不好的原因是，在 Python 中，当您像数字一样使用 False 时，它的计算结果为 0。尝试在解释器中运行这些:

False * 5 # => 0
False + 5 # => 5
False == 0 # => True
False is 0 # => False

这意味着，如果您的代码以其他方式工作并且搜索不成功，您仍然会在很多时候返回一个整数答案。在添加 mid 时，False 值将会丢失。为了避免这种情况，我下面给出的代码不使用递归，因此 return False 是最终的。它直接转到首先调用 binary_search 的人，而不是任何之前的递归调用。您仍然可以编写递归解决方案，但几乎肯定需要进行类似 if binary_search(...) is False: 的比较，然后 在代码中的某个位置需要担心 is 和 == 之间的差异然后您可能会想更频繁地使用 is，这是一个坏主意。

我还认为 a_list[mid:] 也存在一些问题。我没有确认这一点，但我认为您希望 a_list[mid+1:] 排除您已确认不是您要查找的元素的中间元素。不管怎样，我的替代代码根本不使用切片，所以我不会担心它。

这是我相信可以满足您要求的代码。

def binary_search(a_list, item):

    if not a_list:
        return False

    mid = len(a_list)//2
    start = 0 # new and important
    end = len(a_list) # new and important

    while start < end: # new and important
        if a_list[mid] > item:
            end = mid
            mid = (end - start) // 2 # new and important
        elif a_list[mid] < item:
            start = mid + 1
            mid = start + (end - start) // 2 # new and important
        else:
            return mid

    return False

请注意递归调用的删除以及 start 和 end 的添加。它们跟踪您正在搜索列表的哪一部分，而不是您之前使用的列表切片。