Мои функции деления пополам имеют маленькую ошибку - PullRequest
Новая
       30

Мои функции деления пополам имеют маленькую ошибку

0 голосов
/ 18 июня 2019

Мои рекурсивные и итеративные функции деления пополам не будут работать с длинными списками с одинаковым номером. 

def bisection_it(mylist, goal):
    start, end = 0, (len(mylist) - 1)
    while start <= end:
        mid = (start + end) // 2
        if goal == mylist[mid]:
            return mid
        if goal < mylist[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1


def bisection_rec(mylist, goal, start = 0, end = None):
    if end is None:
        end = len(mylist) - 1
    if start > end:
        return -1

    mid = (start + end) // 2
    if goal == mylist[mid]:
        return mid
    if goal < mylist[mid]:
        return bisection_rec(mylist, goal, start = 0, end = mid-1)
    return bisection_rec(mylist, goal, mid+1, end)

со списком [2, 2, 2, 2, 2, 2, 2, 2, 2,] Я ожидаю, что выходной сигнал будет равен 0, но фактический выходной сигнал равен 4

...