1

我运行一个带有函数的while循环来检查变量i是否高于列表的len。我把它放在那里作为停止循环的一种方式，但它没有检查它。由于它不会自行结束，因此我必须在其中放置一个返回 false 的 if 条件。

def binarySearch(numberlist, number):
    first = 0
    last = len(numberlist)-1
    found = False
    i=0

    while found == False or i <= len(numberlist):
        i = i + 1
        mid = (first + last) // 2
        print(numberlist[mid])
        if i > len(numberlist)+1:
            return False
        if mid < first or mid > last or mid < 0:
            return False
        if number == numberlist[mid] or number == numberlist[first] or number == numberlist[last] :
            return True
        elif number < numberlist[mid]:
            last = mid
        elif number > numberlist[mid]:
            first = mid
    return False
4

1 回答 1

1

错误在于以下几行。

elif number < numberlist[mid]:
    last = mid
elif number > numberlist[mid]:
    first = mid

考虑我们正在寻找不在列表中的数字的情况。

指针first,last和mid最终都会收敛到某个索引。在这种情况下，最后两个条件之一将是True，但由于所有三个值都已经相等，指针不再更新，我们进入无限循环。

为确保不会发生这种情况，我们必须根据条件设置为或来确保间隔始终减小大小。然后，如果变得大于 ，我们可以停止循环。firstmid + 1lastmid - 1firstlast

def binary_search(numberlist, number):
    first, last = 0, len(numberlist) - 1

    while first <= last:
        mid = (first + last) // 2
        if numberlist[mid] == number:
            return True
        elif numberlist[mid] > number:
            last = mid - 1
        else:
            first = mid + 1

    return False
于 2018-12-18T20:34:06.790 回答