递归二分查找的递归与比较次数统计错误排查请求

递归次数统计错误的核心原因 #

你实际输出的递归次数比预期少1，大概率是统计时机和定义不匹配：

• 预期的recursions:2应该是把**所有函数调用（包括初始调用）**都计入次数；而你的统计逻辑可能只在函数内部触发递归调用时才计数，漏掉了初始调用。
• 以测试用例为例：初始调用查找整个数组（未被计数）→ 第一次递归调用查找左半区（计数+1），最终得到recursions:1，和你实际输出一致。

比较次数统计错误的核心原因 #

实际输出的比较次数比预期少1，通常是统计的比较范围和预期不一致：

• 预期的comparisons:3应该是把每一次分支判断的比较都单独计数。比如找目标2的流程中：
  1. 中间值5和2比较（判断是否相等，第1次）
  2. 判断5是否大于2（第2次）
  3. 中间值2和2比较（判断是否相等，第3次）
• 而你的统计逻辑可能只把“中间值与目标的直接数值比较”算一次，比如把“是否相等+是否大于”合并为一次比较，最终只统计到2次。

修正方向参考 #

如果要匹配预期的统计结果，调整统计逻辑即可：

1. 递归次数：在函数入口处就递增计数（不管是初始调用还是递归调用），确保所有调用都被统计。
2. 比较次数：把每一次针对目标值的分支判断都单独计数，比如判断arr[mid] == target、arr[mid] > target时各算一次比较。

示例修正伪代码：

def binary_search(arr, target, low, high, recursions, comparisons):
    recursions += 1  # 进入函数就计数，覆盖初始调用
    if low > high:
        return (-1, recursions, comparisons)
    
    mid = (low + high) // 2
    comparisons += 1  # 统计相等判断的比较
    if arr[mid] == target:
        return (mid, recursions, comparisons)
    
    comparisons += 1  # 统计大于判断的比较
    if arr[mid] > target:
        return binary_search(arr, target, low, mid-1, recursions, comparisons)
    else:
        comparisons += 1  # 统计小于判断的比较（若走此分支）
        return binary_search(arr, target, mid+1, high, recursions, comparisons)

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