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

Question

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

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 是否等于我们的目标。我也不明白为什么我不应该检查开始和结束。

此外，上面的代码，即使它找到了目标的索引，当递归结束时它也不会正确return。

非常感谢任何建议。我想重复一遍，我意识到我没有指定二进制搜索应该运行的哪一边，但是，我只是想了解为什么它甚至 return 没有任何价值。

谢谢。

Answer 1

您 return 仅针对基本情况的值。在 "normal" 个案例中

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

你return什么都没有。因此，当您按照自己的方式将堆栈返回到原始调用时，没有 return 值。尝试

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

Answer 2

它不会 return 任何值，因为除非您找到该元素，否则您不会 return 任何东西，因此如果在第一次调用时它没有找到该元素，则什么也不会return编辑。要继续以递归方式查找值，您应该在递归调用函数之前添加 return，例如：

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
    s1 = bin_search(mid, end-1, nums, target)
    if s1 >= 0:
        return s1
    return bin_search(start+1, mid, nums, target)

但是，您应该着手实施二分查找。例如，当你没有找到元素时，你应该选择去哪里，并将两次调用减少到一次调用。我还建议尝试二进制搜索的迭代方法，例如：

def bin_search(start, end, nums, target):
    # suppose we're just looking for the number in a sorted array
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            end = mid-1
        else:
            start = mid+1
    return -1

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

How to properly recursively call alternative type of binary search (python)?

python

recursion

binary-search