Python递归二分查找函数返回-1异常求助：条件判断问题排查

你的递归二分查找函数的核心错误出在右半区间的递归调用参数上：

当key > A[M]时，你需要搜索的是[M+1, R]这个右半区间，但代码里错误地写成了保持左边界L不变、把右边界设为M+1，也就是搜索[L, M+1]。这个错误会导致递归过程中搜索区间逐渐向左收缩，最终出现key > A[R]的情况，触发你设置的边界判断条件，直接返回-1。

错误流程演示 #

以你的测试用例为例：

1. 初始调用：L=0, R=6, M=3，A[M]=62，key=71>62，错误调用recur_binary_search(A,0,4,key)
2. 第二次调用：L=0, R=4, M=2，A[M]=59，key=71>59，错误调用recur_binary_search(A,0,3,key)
3. 第三次调用：L=0, R=3，此时A[R]=62，key=71>62，触发边界判断条件，返回-1

修正后的代码 #

A = [31,48,59,62,71,75,81]
L=0
R=len(A)-1
key = 71

def recur_binary_search(A, L, R, key):
  if key < A[L] or key > A[R]:
    return -1
  M = (L + R) // 2
  if key < A[M]:
    return recur_binary_search(A,L,M-1,key)
  elif key > A[M]:
    # 修正：搜索右半区间，左边界设为M+1，右边界保持R不变
    return recur_binary_search(A,M+1,R,key)
  else:
    return M

print( recur_binary_search(A, L, R, key))
# 输出：4

补充说明 #

二分查找的核心是每次根据中间值精准缩小搜索区间：

• 当key < A[M]：搜索左半区间[L, M-1]（原代码此处正确）
• 当key > A[M]：搜索右半区间[M+1, R]（原代码此处错误）
• 当值相等时直接返回当前索引

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