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))

Supposing middle_index is start or end (as is likely). Your next call will need to check the case where end < start — Kenny Ostrom, Nov 06 '20 at 19:28
it works this way but can't see why it crashes for some non existing input while work's with some non existing inputs like ```15``` , ```100``` or ```8``` can't see the reason — KMG, Nov 06 '20 at 19:33
Well, what do you see in your tracing output? You didn't include that in your post. That output should show the problems pretty quickly. — Prune, Nov 06 '20 at 19:34
Binary search is harder than it looks. Check out https://stackoverflow.com/q/504335/5987 or https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ — Mark Ransom, Nov 06 '20 at 19:49

score 1 · Accepted Answer · answered Nov 06 '20 at 19:35

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

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

1 Answers1