递归二分搜索检索目标的索引

Question

我试着用二分法搜索索引

def bi_search(nums: List[int], find: int) -> int:
    """
    Return the index of the find 
    """
    if len(nums) == 0:
        return -1
    else:
        mid = len(nums) // 2  #testEntry
        if find == nums[mid]:
            return mid 
        if find < nums[mid]:
            sub_nums = nums[:mid]
            return bi_search(sub_nums, find)  

        if find > nums[mid]:
            sub_nums = nums[mid:]
            return bi_search(sub_nums, find) #recursive case.

但它并没有像预期的那样起作用

In [26]: bi_search(list(range(1000)), 777)                     
Out[26]: 4

它返回基本情况的中间。你知道吗

我注意到可以使用迭代方法检索正确的索引，如bisect — Array bisection algorithm — Python 3.7.3rc1 documentation

在递归解决方案中有可能得到正确的索引吗？你知道吗

Answer 1

如果将print()语句添加到函数中并使用较小的示例，则可以看到问题：

def bi_search(nums, find):
    print((nums, find))
    ...

print(bi_search(list(range(10)), 7))

输出：

([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 7)   # Looks good.
([5, 6, 7, 8, 9], 7)                  # Also good.
2                                     # Doh!

问题是返回的是上次选中的列表中的索引，而不是初始列表的索引。为了使您的方法起作用，您需要通过递归调用传递更多的信息，这会变得很棘手。你知道吗

另一种不同的方法是为每个调用传递完整的列表，并在执行时调整搜索的上下限。这样做还有一个好处，即避免在每次调用时创建新的列表。例如：

def bi_search(nums, find, i = None, j = None):
    # Setup.
    N = len(nums)
    if i is None:
        i = 0
        j = N - 1
    # Base case for failure.
    if j < i:
        return None
    # Success or recurse.
    mid = (i + j) // 2
    if find == nums[mid]:
        return mid 
    elif find < nums[mid]:
        return bi_search(nums, find, i, mid - 1)
    else:
        return bi_search(nums, find, mid + 1, j)