时间戳

首页 > 解决方案 > 如何正确递归调用替代类型的二进制搜索（python）？

python - 如何正确递归调用替代类型的二进制搜索（python）？

问题描述

我了解了二进制搜索的要点，但我无法理解为什么这个不完整的代码（因为我没有指定我希望搜索运行的一侧）代码甚至不会返回任何值（例如对于小列表长度）。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def bin_search(start, end, nums, target):
            mid = int((start+end)/2)
            if start >= end:
                return -1     
            if nums[mid] == target:
                return mid
            elif nums[start] == target:
                return start
            elif nums[end] == target:
                return end
            bin_search(mid, end-1, nums, target)
            bin_search(start+1, mid, nums, target)


        output = bin_search(0, len(nums)-1, nums, target)
        return output

取自以下 leetcode：https ://leetcode.com/problems/search-in-rotated-sorted-array/

我知道这应该是什么样子 - 在这些情况下，人们只检查 sub_list 的 MID 是否等于我们的目标。我不明白为什么我也不应该检查开始和结束。

此外，上面的代码，即使找到目标的索引，递归结束后也不会正确返回。

任何意见是极大的赞赏。我确实想重复一遍，我意识到我没有指定二进制搜索应该在哪一侧运行，但是，我只是想理解为什么它甚至不会返回任何值。

谢谢。

标签： pythonrecursionbinary-search

解决方案

您只为基本情况返回一个值。在“正常”情况下

        bin_search(mid, end-1, nums, target)
        bin_search(start+1, mid, nums, target)

你什么都不返回。因此，当您将堆栈备份到原始调用时，没有返回值。尝试

        r_search = bin_search(mid, end-1, nums, target)
        l_search = bin_search(start+1, mid, nums, target)
        return max(r_search, l_search)

推荐阅读