为什么python中的递归二进制搜索函数不起作用

BLINAK • 3 年前 • 1454 次点击

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

应返回:

-1

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/129258

文章 [ 3 ] | 最新文章 3 年前

• 1 楼

MaxPC08 3 年前

你需要在第二次返回时签上标签。尝试:

                            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.

• 2 楼

BrokenBenchmark 3 年前

您需要将递归调用的结果返回给 binary_search_recursive() :

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

应该是

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

请注意,这是不二进制搜索算法;一次只枚举一个元素(使用递归),所以这实际上是一个顺序搜索。

• 3 楼

Lrrr 3 年前

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

登录后回复