为什么递归二进制搜索有时会导致一些但不是所有不存在的输入的堆栈溢出？

Question

我正在实现一个递归 python 二进制搜索函数，它适用于大多数输入，但似乎会导致一些但不是所有不存在的列表元素发生堆栈溢出，我不明白为什么会出现这种行为代码是

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

列表是 sorted_list = [1, 2, 3, 4, 4, 7, 9, 10, 14, 80] 似乎会导致溢出的输入是 6 11 和 return False 对于像 8 这样的输入来说是正常的和 100 和 15 。该函数被称为 print(recursive_binary_search(0, len(sorted_list)-1, 11, sorted_list))

Answer 1

当 start 和 end 相差一个索引时，您会遇到问题。在您给出的示例中，当您达到 start=8 和 end=9 时，您将拥有 middle_index=8，然后如果 array[middle_index] > search，您将使用 start=8和end=7，这是无效的，将永远递归。

您可以通过放宽结束条件以使用 <= 而不是 == 来修复此无限递归：

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

旁注 - 这种情况可以简化如下：

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

为什么递归二进制搜索有时会导致一些但不是所有不存在的输入的堆栈溢出？

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

python

algorithm

recursion

binary-search