如何推导二分查找递归实现的时间复杂度递推关系式
本文详解二分查找递归版本的递推关系式（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] 并决定向左或右子区间递归——仅执行一次递归调用（非左右同时），且子区间长度至多为 $\left\lfloor \frac{n}{2} \right\rfloor$（严格来说是 $\lceil n/2 \rceil - 1$ 或 $\lfloor n/2 \rfloor - 1$，但渐进意义下等价于 $n/2$）；
- 每层递归中的非递归操作（索引计算、比较、分支判断）均为常数时间 $O(1)$。
因此，设 $T(n)$ 表示处理长度为 $n$ 的有序子数组所需最坏时间，则其递推关系为：
[
T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + O(1), \quad \text{其中 } T(1) = O(1)
]
在渐进分析中，可简化写作：
[
\boxed{T(n) = T\left(\frac{n}{2}\right) + O(1)}
]
这正是选项中唯一正确的答案：$T(n) = T(n/2) + O(1)$。
Socratic Lab
AI驱动的在线知识社区和AI知识搜索平台
⚠️ 注意事项：
- ❌ 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）的典范表达。