Почему я получаю ошибку «RecursionError: максимальная глубина рекурсии превышена при сравнении» в этом Python двоичном поиске?

Question

Я написал этот двоичный поиск как задачу для моего Uni:

def bin_search(l,i,start,end):
    if start >= end:
        return False
    else:
        pos = (start + end) // 2
        if i == l[pos]:
            return True
        elif i < l[pos]:
            return bin_search(l,i,start,pos)
        else:
            return bin_search(l,i,pos,end)

Я все время получаю сообщение об ошибке RecursionError: maximum recursion depth exceeded in comparison. Если я изменю последнюю строку на:

         return bin_search(l,i,pos + 1,end)

, этого не произойдет, я не понимаю, почему это происходит, потому что, как я понял, в неработающем коде должен быть тот же диапазон списка плюс еще один задано как параметр. Подскажите, пожалуйста, в чем моя ошибка.

Answer 1

Попробуйте следующее:

def bin_search(l,i,start = 0,end):
    if start >= end:
        return False
    else:
        pos = (start + end) // 2
        if i == l[pos]:
            return True
        elif i < l[pos]:
            return bin_search(l,i,start + 1,pos)
        else:
            return bin_search(l,i,pos + 1,end)