Python递归二分查找触发终止条件仍执行else分支问题排查

你的代码错误出在右半区间递归结果的处理逻辑：当右半区间的递归调用最终返回-1（代表未查询到目标值）时，代码直接执行了mid + 递归返回值，将mid与-1做加法得到了正整数的错误索引，没有把-1向上传递，才会出现找不到元素却返回正数索引的问题。

以你测试用例x=5为例，执行流程如下：

• 第一层调用：arr=[2,3,4,10,40]，mid=2，arr[mid]=4 < 5，进入else分支，等待2 + binary_search([4,10,40],5)的结果
• 第二层调用：arr=[4,10,40]，mid=1，arr[mid]=10 >5，进入左递归分支，等待binary_search([4],5)的结果
• 第三层调用：arr=[4]，满足终止判断条件，正确返回-1
• 第二层调用收到返回值-1，直接向上返回-1
• 第一层调用执行2 + (-1)计算，得到错误结果1

x=50的错误结果也是相同逻辑导致的。

只需要修改else分支的处理逻辑，先判断下层递归的返回值是否为-1，如果是则直接向上返回-1，否则再叠加mid值：

def binary_search(arr, n):
    mid = len(arr) // 2

    if len(arr) == 1 and arr[mid] != n:
        return -1

    elif n == arr[mid]:
        return mid  

    elif n < arr[mid]:
        return binary_search(arr[:mid], n)

    else:
        # 新增返回值判断，避免把-1和mid相加
        sub_res = binary_search(arr[mid:], n)
        return sub_res if sub_res == -1 else mid + sub_res

修改后测试所有用例都会返回正确结果：

• x=1返回-1
• x=5返回-1
• x=50返回-1
• 存在的元素返回对应索引

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