Python递归二分查找函数返回None问题排查求助

你的代码核心问题是递归分支没有返回递归调用的结果，导致子函数找到正确索引后，无法将结果传递回上层调用，顶层函数因没有显式返回值，默认返回None。

测试用例执行过程拆解 #

调用binarysearch([0,2,4,5],2)时：

1. 初始数组长度为4，mid=2，a[mid]=4，由于2<4，进入elif(n<a[mid])分支，调用binarysearch([0,2],2)，但此处没有返回该调用的结果。
2. 在子调用binarysearch([0,2],2)中，数组长度为2，mid=1，a[mid]=2，匹配成功，返回1，但这个结果没有被上层调用接收并返回，因此顶层函数最终返回None。

修复后的代码 #

给递归分支的调用加上return，让结果逐层传递回顶层：

def binarysearch(a,n):
    mid = int(len(a)/2) # taking the middle point
    if n == a[mid]: 
        return mid
    elif n > a[mid]: # 目标值更大，在右半部分查找
        return binarysearch(a[(mid+1):], n)
    elif n < a[mid]: # 目标值更小，在左半部分查找
        return binarysearch(a[0:mid], n)

额外提示 #

当前修复后的代码仍存在边界问题：如果查找的元素不在数组中，递归到空数组时会触发IndexError（访问a[mid]时数组为空），可以添加数组为空的判断来优化：

def binarysearch(a,n):
    if not a:
        return -1 # 表示未找到
    mid = int(len(a)/2)
    if n == a[mid]: 
        return mid
    elif n > a[mid]:
        return binarysearch(a[(mid+1):], n)
    elif n < a[mid]:
        return binarysearch(a[0:mid], n)

内容的提问来源于stack exchange，提问作者maths and chess