为什么我的递归搜索功能不起作用？

Question

我需要编写一个简单的递归函数，从索引：左到索引：右搜索数组。我们不必担心无效的左右输入，它们总是正确的。如果数组中有一个值等于该键，则它 return 是该值的索引。如果键不在数组中，它 returns -1. 我真的不知道为什么我的功能不起作用。我认为应该。仅当键是数组的第一个索引时才有效。

def binary_search_recursive(array: List[int], left: int, right: int,
                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            binary_search_recursive(array, left + 1, right, key)
    return -1

测试：

binary_search_recursive([0,1,5,6,23,45], 0, 5, 5)

应该return:

Returns:

-1

Answer 1

您需要在第二个 return 中切换。尝试：

                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            binary_search_recursive(array, left + 1, right, key)
            return -1 #Moved to the right.

Answer 2

要修复您的代码，您需要 return else 语句：

def binary_search_recursive(array: list[int], left: int, right: int,
                            key: int) -> int:
    if left <= right:
        if array[left] == key:
            return left
        else:
            return binary_search_recursive(array, left + 1, right, key)
    return -1

但是，它仍然不是二进制搜索。

编辑： 真正的二分查找应该是这样的：

def binary_search_recursive(array: list[int], left: int, right: int,
                            key: int) -> int:
    if right >= left:

        center = (right + left) // 2

        if array[center] == key:
            return center

        elif array[center] > key:
            return binary_search_recursive(array, left, center - 1, key)
        else:
            return binary_search_recursive(array, center + 1, right, key)
    return -1

Answer 3

你需要return递归调用的结果binary_search_recursive():

binary_search_recursive(array, left + 1, right, key)

应该是

return binary_search_recursive(array, left + 1, right, key)

请注意，这不是二进制搜索算法；您一次枚举一个元素（使用递归），所以这实际上是一个顺序搜索。

为什么我的递归搜索功能不起作用？

Why is my recursive search function not working?

python

recursion