本文详解二分查找递归版本的递推关系式（recurrence relation）推导过程，明确问题规模的正确定义，指出常见误解，并给出严谨的数学表达与分析。
在分析递归算法的时间复杂度时，建立准确的递推关系式（Recurrence Relation）是关键一步。以经典的二分查找递归实现为例：
def b(arr, target, low, high): if low > high: return -1 mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return b(arr, target, low, mid - 1) else: return b(arr, target, mid + 1, high)初学者常误认为：由于 arr 参数始终传入整个数组（未切片、未复制），因此“输入规模未减小”，进而错误推断递推式不满足分治形式。但这是对问题规模（problem size）的根本性误解。
✅ 正确理解：算法的实际工作范围由参数 low 和 high 决定，每次递归调用仅在子区间 [low, high] 内操作，真正参与比较和计算的元素个数为
[ n = text{high} – text{low} + 1 ]
该值即为当前递归层的有效输入规模。
- 基准情况（base case）：当 low > high 时，区间为空，操作时间为常数 $O(1)$；
- 递归情况：计算 mid、比较 arr[mid] 并决定向左或右子区间递归——仅执行一次递归调用（非左右同时），且子区间长度至多为 $leftlfloor frac{n}{2} rightrfloor$（严格来说是 $lceil n/2 rceil – 1$ 或 $lfloor n/2 rfloor – 1$，但渐进意义下等价于 $n/2$）；
- 每层递归中的非递归操作（索引计算、比较、分支判断）均为常数时间 $O(1)$。
因此，设 $T(n)$ 表示处理长度为 $n$ 的有序子数组所需最坏时间，则其递推关系为： [ T(n) = Tleft(leftlfloor frac{n}{2} rightrfloorright) + O(1), quad text{其中 } T(1) = O(1) ]
在渐进分析中，可简化写作： [ boxed{T(n) = Tleft(frac{n}{2}right) + O(1)} ]
这正是选项中唯一正确的答案：$T(n) = T(n/2) + O(1)$。
⚠️ 注意事项：
- ❌ T(n) = 2T(n/2) + O(1) 描述的是如归并排序这类双路递归算法，而二分查找每次只进入一个子问题，故系数为 1，非 2；
- ❌ T(n) = 2T(n-1) + O(1) 对应线性递减但双分支的错误建模（如未剪枝的暴力搜索）；
- ❌ T(n) = T(n/2) + O(n) 错误高估了每层开销（实际为 $O(1)$，非遍历整个数组）；
- 数组是否被物理切片（如 arr[:mid]）不影响递推式本质——只要逻辑上问题规模减半且仅单路递归，递推式即成立。
通过主定理（Master Theorem）求解该递推式：
$a = 1, b = 2, f(n) = O(1)$，满足 $f(n) = O(n^{log_b a – varepsilon}) = O(n^{0 – varepsilon})$，故 $T(n) = Theta(log n)$，与二分查找的经典时间复杂度完全一致。
总结：推导递推关系式时，务必基于算法实际作用的输入规模（由控制参数界定），而非函数签名中出现的全部参数；二分查找的精髓在于“单路减半”，其递推式简洁而有力——$T(n) = T(n/2) + O(1)$，是分治思想中“减而治之”（decrease-and-conquer）的典范表达。