В бинарном поиске, почему мой цикл бесконечен?

Question

Я запускаю цикл while с функцией, чтобы проверить, больше ли переменная i, чем длина списка.Я поместил его туда как способ остановить цикл, но он не проверяет его.Поскольку это не заканчивается само по себе, я должен был поместить условие if внутри, которое возвращает false.

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 или last до 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