本文准确解析二分查找递归实现的递推关系式，阐明为何问题规模是当前搜索区间的长度而非原数组长度，并指出正确选项为 $ t(n) = t(n/2) + o(1) $。
二分查找是一种典型的分治算法，其核心思想是每次将搜索区间缩小一半。虽然函数参数中始终传入整个数组 arr，但实际参与计算的有效数据范围由 low 和 high 严格界定。因此，递推关系中的问题规模 $ n $ 应定义为当前子问题的区间长度：
$$
n = \text{high} - \text{low} + 1
$$
观察函数逻辑：
- 每次递归调用仅进入一个分支（mid - 1 或 mid + 1），不会同时递归左右两半；
- 区间长度从 $ n $ 缩减为约 $ \lfloor n/2 \rfloor $（因 mid = (low + high) // 2，故 mid - 1 - low + 1 ≈ n/2，同理右半亦然）；
- 所有操作（比较、计算 mid、边界判断）均为常数时间，即 $ O(1) $。
由此可得标准递推式：
$$
T(n) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + O(1)
$$
忽略取整后，简写为：
$$
T(n) = T\left(\frac{n}{2}\right) + O(1)
$$
✅ 正确选项即为：$ T(n) = T(n/2) + O(1) $
❌ 常见误解辨析：
- ❌ $ T(n) = 2T(n/2) + O(1) $：对应归并排序等需双路递归的算法，二分查找仅单路递归；
- ❌ $ T(n) = 2T(n-1) + O(1) $：暗示线性缩减且双分支，与二分逻辑完全不符；
- ❌ “数组未被切割所以规模不变”：错误。算法分析关注输入规模的渐进变化，而 low/high 显式刻画了当前子问题规模，这才是递推建模的依据。
? 补充说明：该递推式解为 $ T(n) = O(\log n) $，可通过主定理（Master Theorem）验证：
- $ a = 1, b = 2, f(n) = O(1) $，满足 $ \log_b a = \log_2 1 = 0 $，且 $ f(n) = \Theta(n^0) $，故 $ T(n) = \Theta(\log n) $。
# 示例：跟踪递归深度，直观验证区间缩减
def b(arr, target, low, high, depth=0):
print(" " * depth + f"call: low={low}, high={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, depth + 1)
else:
return b(arr, target, mid + 1, high, depth + 1)
# 测试：b([1,3,5,7,9], 7, 0, 4)
# 输出将显示 size: 5 → 2 → 1 → 0，清晰体现每次规模约减半总结：构建递推关系的关键在于精准识别子问题规模的定义与变化规律，而非仅看函数参数表象。对二分查找而言，low 与 high 共同决定有效输入规模，每一次递归都将该规模减半，最终导出简洁而有力的 $ T(n) = T(n/2) + O(1) $ 关系式。
