递归二分查找实现无法覆盖所有用例，求排查与解决思路

关键错误点 #

• 初始调用的偏移量逻辑错误：search方法里把中间索引直接作为answer传入递归完全不合理——只有当中间元素等于target时才返回该索引，否则这个值和目标位置毫无关系。右半区初始偏移设为0更是错误，此时目标若在右半区，初始偏移应该是中间位置+1。
• 终止条件缺失且逻辑错误：
  • 未处理子数组为空的情况，会导致访问nums[n//2]抛出索引越界异常；
  • 子数组长度为1且等于target时，没有对应返回逻辑，会跳过判断进入后续分支。
• 递归返回值处理失误：当递归返回-1（未找到）时，直接将answer赋值为-1返回，会覆盖上层的正确逻辑，导致原本能找到的情况也返回错误结果。
• 特殊场景未覆盖：空数组时search方法访问nums[0]会报错；中间元素就是target的情况，初始判断未直接返回，反而进入递归绕路。

修正后的代码 #

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

class Solution(object):
    def search(self, nums, target):
        return binary(nums, target, 0)

修正逻辑说明 #

• 移除search中多余的初始判断，统一以偏移量0调用递归，逻辑更简洁统一；
• 递归函数优先判断数组是否为空，直接返回-1避免报错；
• 找到目标时，返回原数组偏移量+当前子数组的中间索引，确保是原数组中的正确位置；
• 左半区递归时偏移量不变，右半区递归时偏移量加上左半区的总长度（mid+1），保证偏移计算准确；
• 终止条件覆盖所有边界场景，逻辑闭环。

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