本文准确推导标准二分查找递归实现的递推关系式，澄清“数组未被分割”导致问题规模不变的常见误解，指出正确形式为 $ t(n) = t(n/2) + o(1) $，并结合代码逻辑与数学定义给出严谨解释。
二分查找虽操作于同一数组对象，但其有效求解范围严格由参数 low 和 high 界定。每次递归调用均将搜索区间收缩至前半段或后半段：当 arr[mid] > target 时，新子问题为 b(arr, target, low, mid - 1)，区间长度从 $ n = \text{high} - \text{low} + 1 $ 缩减为 $ (\text{mid} - 1) - \text{low} + 1 \approx n/2 $；同理，arr[mid] 问题规模（即当前搜索区间的元素个数）在每层递归中严格减半，而非保持不变。
该行为直接对应主定理（Master Theorem）的标准形式：
$$
T(n) = T\left(\frac{n}{2}\right) + O(1)
$$
其中：
- $ T(n/2) $ 表示单次递归调用（非两次！），因每次执行仅进入左或右一个子区间；
- $ O(1) $ 代表本次调用中的常数时间操作：边界判断、中点计算、一次比较及索引更新。
✅ 正确选项：$ T(n) = T(n/2) + O(1) $
需特别注意以下常见误区：
- ❌ “数组未切片，故规模不变”：错。算法复杂度分析关注逻辑问题规模（活跃区间长度），而非物理内存占用；
- ❌ “有两个递归分支，所以是 $ 2T(n/2) $”：错。二分查找是尾递归，每次仅执行一个分支，不存在并行或分治式双路递归；
- ❌ 混淆 $ n $ 的定义：此处 $ n $ 应定义为初始调用时的 high - low + 1，即当前搜索区间的长度，而非整个数组长度（即使传入全长数组，后续调用中 $ n $ 仍持续减半）。
下面通过简化版代码验证区间收缩逻辑：
def b(arr, target, low, high):
print(f"Current range: [{low}, {high}], size = {high - low + 1}") # 调试输出
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) # 区间变为 [low, mid-1]
else:
return b(arr, target, mid + 1, high) # 区间变为 [mid+1, high]
# 示例：在 [1,3,5,7,9] 中查找 7
# 输出将显示：[0,4]→[3,4]→[3,3]→[4,3]（终止），尺寸依次为 5→2→1→0综上，二分查找递归版本的递推关系本质刻画了单路径、等量缩减的问题求解过程。其时间复杂度为 $ O(\log n) $，由递推式 $ T(n) = T(n/2) + O(1) $ 解得。掌握这一关系，是理解分治策略与递归分析的基础，也是区分二分查找与真正分治算法（如归并排序：$ T(n) = 2T(n/2) + O(n) $）的关键所在。
