python - 如何在 python (递归) 中进行二进制搜索，但不包括列表的最大值和最小值？

Question

我一直想进行二进制搜索(通过递归)，但我不知道为什么我的代码不起作用...任何人都可以请更正我的代码并说明它不起作用的原因吗？？

正如您在我的代码中看到的那样，我在每次递归时对字符串进行切片，最后当找到目标时，我将返回目标的位置..

def binary(n,target):
    n.sort()
    mid = (0 + (len(n)-1))//2
    if target == n[mid]:
        return mid
    elif target < n[mid]:
        return binary(n[:mid],target)
    elif target > n[mid]:
        return binary(n[mid:],target)

这是我收到的错误信息...RecursionError:调用 Python 对象时超出最大递归深度。

Answer 1

有两个问题，都在最后一行:

def binary(n, target):
    n.sort()
    mid = (0 + (len(n) - 1)) // 2
    if target == n[mid]:
        return mid
    elif target < n[mid]:
        return binary(n[:mid], target)
    elif target > n[mid]:
        return mid + 1 + binary(n[mid + 1:],target)
                ^^^^^^^^                ^

1. 由于您正在切片，并且为了在原始排序列表中提供索引，我们需要跟踪我们在递归时“丢失”的索引
2. n[:mid] 的完整形式是 n[mid+1:] - 而不是 n[mid:] 因为你已经检查目标(在中间)并希望将其从 future 的迭代中删除 - 顺便说一下，这是导致无限循环的原因!

由于我们在 mid+1 处对列表进行切片，因此我们需要在递归调用之前添加 mid+1，以便保留列表右侧的项目索引:

[1,2,3,4,5]
     ^ say we slice here and get [4,5]
       we want to save the indexes so we'll add mid (2) + 1 since now in [4,5] the item 4 will get the index zero

评论:通过在每次迭代时调用 n.sort()，我们“失去”了二进制搜索的所有优势，因为即使在列表排序之后，重新排序也至少需要在)。因此，如果我们需要先排序，我们不妨迭代数组直到找到/找不到该项目。或者，如果我们坚持排序，只做一次，然后才递归调用:

n.sort()
binary(n, 2)

binary 不再包含排序:

def binary(n, target):
    mid = (0 + (len(n) - 1)) // 2
    if target == n[mid]:
        return mid
    elif target < n[mid]:
        return binary(n[:mid], target)
    elif target > n[mid]:
        return mid + 1 + binary(n[mid + 1:], target)