使用递归实现BinarySearch方法时触发IndexError错误

你的代码出现索引越界是三个核心问题导致的，对应修复方案如下：

问题1：缺少递归终止条件 #

当递归到数组为空时，len(arr) == 0，此时right = len(arr)-1会得到-1，计算mid = (0 + (-1)) // 2结果为-1，访问arr[mid]必然触发索引越界。必须在函数开头先判断数组是否为空，为空直接返回False（表示找不到目标值）。

问题2：不必要的重复排序 #

二分查找的前提是数组有序，你传入的初始数组已经是有序的，每次递归都调用arr.sort()完全多余——既浪费性能，还可能在递归传递子数组后打乱逻辑（子数组本身已经是有序的，排序操作毫无意义）。

问题3：切片范围错误 #

当目标值小于中间值时，你使用arr[:mid - 1]切片会漏掉mid-1位置的元素，甚至当mid=0时会生成空数组，加速触发索引越界。正确的切片应该是arr[:mid]（Python切片是左闭右开，arr[:mid]对应原数组的[0, mid-1]范围，正好是中间值左侧的所有元素）。

修复后的代码 #

def binarySearch2(arr, val):
    # 终止条件：数组为空，直接返回找不到
    if len(arr) == 0:
        return False
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2
    # 如果无法保证传入数组始终有序，可在外部调用前先排序，递归时无需重复排序
    if val == arr[mid]:
        return True
    elif val > arr[mid]:
        return binarySearch2(arr[mid + 1:], val)
    else:
        return binarySearch2(arr[:mid], val)


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

运行这段代码会输出正确结果：

False
True
True
True
True
True
True
True
True
True

内容的提问来源于stack exchange，提问作者Proteus Yi