使用递归编写二分查找方法时出现IndexError

Question

def binarySearch2(arr, val):
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2
    arr.sort()
    if val == arr[mid]:
        return True
    if val > arr[mid]:
        return binarySearch2(arr[mid + 1:], val)
    if val < arr[mid]:
        return binarySearch2(arr[:mid - 1], val)


for i in range(10):
    print(binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], i))

它一直告诉我“索引超出范围”，我不太确定哪里出错了。

Answer 1

你漏掉了两件事，看看你下面的函数

def binarySearch2(arr, val):
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2

    # Base condition: If the left index crosses the right index, return False
    if left > right:
        return False
    arr.sort()

    if val == arr[mid]:
        return True
    if val > arr[mid]:
        return binarySearch2(arr[mid + 1:], val)
    # If the value is less than the middle element, search the left half
    if val < arr[mid]:
        return binarySearch2(arr[:mid], val)

第一个错误：我们知道，递归函数总是需要一个基本条件，否则会出错（超出最大递归深度）。所以，在这里我们添加了

if left > right:
    return False
# This is the base condition here

第二个错误：

if val < arr[mid]:
   return binarySearch2(arr[:mid - 1], val)

在这里，你不需要 -1。我想给你一个例子，帮助你理解右边的限制：

list(range(1,10))

结果是 [1, 2, 3, 4, 5, 6, 7, 8, 9]。我们知道，右边的限制总是要少1。

Answer 2

在评论中，我提到过：binarySearch2 最后会用一个空的 arr 被调用，这样它的长度就是 0。因为你计算 right = len(arr) - 1，所以 right 就变成了 -1。而 mid = (left + right) // 2 也会变成 -1。这其实是个不好的开始，但用 -1 去索引一个空列表就会导致错误。你的递归函数缺少一个重要的停止条件。

你问为什么会有一个空的 arr。

你的主循环在第一次迭代时是这样调用 binarySearch2 的：

binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], 0)

在这个函数里，这意味着这个条件是 True：

if val < arr[mid]:  # val == 0, mid == 4, 0 < arr[4]
    return binarySearch2(arr[:mid - 1], val)  # called with (arr[:4 - 1], 0)

注意这里有个错误 - 你传入了 arr[:mid - 1]，但因为这个切片已经排除了那个索引的元素，所以你切掉了一个多余的元素。不过这不是主要问题。

在第二次调用时，同样的事情又发生了：

if val < arr[mid]:  # val == 0, mid == 1, 0 < arr[1]
    return binarySearch2(arr[:mid - 1], val)  # called with (arr[:1 - 1], 0)

这已经导致 binarySearch2 被调用为 binarySearch2([], 0)，从而引发了之前提到的错误。

即使你修正了这个错误，把代码改成这样：

    if val < arr[mid]:
        return binarySearch2(arr[:mid], val)

它仍然会失败，因为函数被调用时 val 是 0，而这个值并不在数组里，所以这个条件依然会触发，最终在第三次迭代时调用 binarySearch2([], 0)。

你的代码没有考虑到 val 根本不在列表 arr 里的情况。

一个更好的实现是：

def binarySearch2(arr, val):
    def search(arr, val):
        if len(arr) == 0:
            return False
        left = 0
        right = len(arr) - 1
        mid = (left + right) // 2
        arr.sort()
        if val == arr[mid]:
            return True
        if val > arr[mid]:
            return binarySearch2(arr[mid + 1:], val)
        if val < arr[mid]:
            return binarySearch2(arr[:mid], val)
        
    arr.sort()
    return(search(arr, val))

这样可以避免对列表进行多次排序，并且在继续之前检查 arr 中是否还有值（这是缺失的停止条件）。

还有进一步优化的空间。比如，你不需要一直切片列表 - 你可以只传递左右的索引，并不断缩小它们之间的间距。当然，如果这样做，你也不再需要递归的解决方案，可以用一个简单的循环来完成。