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

Question

此问题已经在这里有了答案：

• Recursive code returns None [duplicate]1个答案

我得到了二进制搜索的要点，但是我很难理解为什么这个incomplete（因为我没有指定要在其上进行搜索的那一面）代码甚至都不会返回任何值（例如长度较小的列表。

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

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

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

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

非常感谢任何建议。我确实想重复一遍，我意识到我没有指定二进制搜索应该在哪一侧运行，但是，我只是在试图理解为什么它甚至不返回任何值。

谢谢。

Answer 1

您仅返回基本案例的值。在“正常”情况下

        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)

Answer 2

它不会返回任何值，因为除非找到该元素，否则您不会返回任何值，因此，如果在第一次调用时未找到该元素，则不会返回任何值。要继续递归查找值，应在递归调用函数之前添加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