Python类内递归二分查找方法返回None而非预期整数的问题
问题根因
出现返回None的核心原因是递归分支未正确透传子递归调用的返回值。Python语言规则中,如果函数执行流走到函数末尾没有遇到显式的return语句,会默认返回None。
对照你的代码逻辑可以定位到具体断层:
- 你在
binary_search方法中处理目标值大于/小于中间值的两个分支时,仅发起了子递归调用,但没有将子调用的返回值作为当前函数的结果向上传递 - 对应代码的问题位置:
elif x>nums[i]: self.binary_search(nums, i+1, end, x) # 子函数的返回值没有被接收、也没有被向上层传递 else: self.binary_search(nums, start, i-1, x) # 同上
结合运行日志可以复现完整的执行链路问题:
- 第一次调用
binary_search时计算出中间下标i=2,因目标值1小于nums[2],触发左区间递归,但该分支没有写return,这层调用没有接住后续递归的返回结果 - 第二次递归走到
start=0、end=1的分支,计算i=0,发现nums[0]与目标值匹配,正常返回了下标0 - 这个返回值回到上一层的递归调用位置时,因为上一层没有写
return接收结果,这层函数走完所有分支后没有其他返回逻辑,直接返回默认的None - 最终
getNum方法拿到的j值就是这个默认返回的None
修复方案
只需要给两个递归分支的调用前加上return关键字,把子递归的结果逐层向上传递即可,修复后的完整可运行代码如下:
class Solution: def getNum(self, nums, x): L_nums = len(nums) j = self.binary_search( nums, 0, L_nums-1, x) print("j=",j) def binary_search(self, nums, start, end, x): print("BS called start=>", start,"end=>", end,"x=>", x) if end==start: if nums[end]==x: return end else: print("called else and returing -1") return -1 i = (end-start)//2 + start print("i=",i) if x==nums[i]: return i elif x>nums[i]: # 增加return透传递归结果 return self.binary_search(nums, i+1, end, x) else: # 增加return透传递归结果 return self.binary_search(nums, start, i-1, x) sol = Solution() sol.getNum([1,3,5,7,9],1)
修复后运行代码,就会正常输出j= 0,匹配目标值对应的下标,不会再返回None。
内容的提问来源于stack exchange,提问作者Prabhav Jani
相关产品推荐
相关产品推荐

