在二进制搜索中，为什么我的循环是无限的？

Question

I 运行一个 while 循环，其功能是检查变量 i 是否高于列表的 len。我把它放在那里作为停止循环的一种方式，但它不检查它。因为它不会自行结束，所以我不得不在 returns 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

Answer 1

错误在以下几行。

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

考虑我们要查找 不在列表 中的号码的情况。

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

为了确保这种情况不会发生，我们必须通过将 first 设置为 mid + 1 或 [=13] 来确保间隔始终减小大小=] 到 mid - 1，具体取决于条件。如果 first 变得大于 last.

，我们就可以停止循环

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

在二进制搜索中，为什么我的循环是无限的？

In binary search, why is my loop infinite?

algorithm

binary-search

python-3.x