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

Question

我需要编写一个简单的递归函数，从索引:左到索引:右搜索数组。我们不必担心左输入和右输入无效，它们总是正确的。如果数组中存在等于键的值，则返回该值的索引。如果该键不在数组中，则返回 -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)

应该返回:

2

返回:

-1

Answer 1

要修复代码，您需要返回 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