Why recursive Binary search sometimes cause stack overflow for some but not all non existing inputs?

Question

I'm implementing a recursive python binary search function That works fine for most inputs but seems to cause stack overflow for some but not all non existing list elements which I can't see why is this behavior the code is

def recursive_binary_search(start: int, end: int, search:int, array: list):
    """
    :param start: start index
    :param end: end index
    :param search: integer to search find
    :param array: Sorted array to search
    :return: True if found, False if Not
    """

    if (end == start) and array[start] != search: return False
    if (end == start) and array[start] == search: return True

    middle_index = (end+start)//2
    if array[middle_index] == search: return True

    elif array[middle_index] > search:
        res = recursive_binary_search(start, middle_index-1, search, array)
        return res
    elif array[middle_index] < search:
        res = recursive_binary_search(middle_index+1, end, search, array)
        return res

the list is sorted_list = [1, 2, 3, 4, 4, 7, 9, 10, 14, 80] inputs seeming to cause overflow are 6 11 and return False as normal for inputs like 8 and 100 and 15 . The function is called as print(recursive_binary_search(0, len(sorted_list)-1, 11, sorted_list))

Answer 1

You have a problem when start and end are one index apart. In the example you've given, when you reach start=8 and end=9, you'll have middle_index=8, then if array[middle_index] > search, you'll call the function with start=8 and end=7, which is invalid, and will recurse forever.

You can fix this infinite recursion by relaxing the end condition to use <= instead of ==:

if (end <= start) and array[start] != search: return False
if (end <= start) and array[start] == search: return True

Side note - this condition could be simplified as follows:

if (end <= start): return array[start] == search