递归实现Python二分查找：左半部分元素无法返回索引问题排查

核心问题点 #

• 递归调用未返回结果：当目标在左半部分时，你调用了binarySearch(array, target)但没有用return传递结果，导致上层函数无法获取到递归找到的索引，最终返回None。
• 索引计算逻辑错误：org_array.index(i)只会返回目标元素第一次出现的位置，若数组有重复元素（比如示例中的两个45），会得到错误的索引；而且每次递归切割数组后，左半区元素在原数组中的起始索引不是0，直接用原数组找索引完全逻辑混乱。
• 偏离二分查找本质：你遍历整个右半区来查找目标，这根本不是二分查找的思路——二分查找的核心是通过比较中间元素快速缩小查找范围，而非遍历半区。

修复后的代码 #

def binarySearch(array, target, left=0, right=None):
    # 初始化右指针为数组最后一个元素的索引
    if right is None:
        right = len(array) - 1
    
    # 查找范围失效，说明目标不存在
    if left > right:
        return -1
    
    # 计算中间位置的索引
    mid = (left + right) // 2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        # 目标在右半区，递归查找右半部分
        return binarySearch(array, target, mid + 1, right)
    else:
        # 目标在左半区，递归查找左半部分
        return binarySearch(array, target, left, mid - 1)

# 测试示例
print(binarySearch([0,1,21,33,45,45,61,71,72,73,74], 21))  # 输出2

修复说明 #

• 用left和right指针跟踪原数组的查找范围，直接通过mid就能拿到原数组的正确索引，无需拷贝数组。
• 递归调用时明确返回结果，确保找到的索引能逐层传递回初始调用。
• 严格遵循二分查找逻辑：通过中间元素与目标的比较，快速将查找范围缩小一半，时间复杂度保持O(logn)。
• 处理了目标不存在的情况，返回-1作为标识。

内容的提问来源于stack exchange，提问作者Vineet Vinayak