二分查找与主定理：为什么 log n 是分治的标准答案

图：二分查找递归式 T(n)=T(n/2)+1，主定理情况2 直接得 Θ(log n)

二分查找每次取中点、丢弃一半区间，规模 $n\to n/2$。递推式 $T(n)=T(n/2)+\Theta(1)$：$a=1,b=2$，临界值 $n^{\log_2 1}=1$，$f(n)=1=\Theta(1\cdot\log^0 n)$ 属情况2，直接得 $\Theta(\log n)$。

为什么是"标准答案"

任何"每次把规模除以常数"的分治，层数都是 $\Theta(\log n)$；只要每层代价是 $O(1)$ 或 $O(n)$ 线性合并，总代价就是 $\Theta(\log n)$ 或 $\Theta(n\log n)$。对数与 $n\log n$ 就是分治的两张"标准名片"。

参考代码：递归版二分查找

def bisect(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    if lo >= hi:
        return lo                      # 未找到，返回插入点
    mid = (lo + hi) // 2
    if a[mid] == x:
        return mid
    if a[mid] < x:
        return bisect(a, x, mid + 1, hi)   # T(n)=T(n/2)+Θ(1) ⇒ Θ(log n)
    return bisect(a, x, lo, mid)

print(bisect([1, 3, 5, 7, 9], 5))   # 2

注意：迭代写法和递归复杂度一样，但迭代只占 $O(1)$ 栈，不会像深层递归那样爆栈（见热点⑧）。

关联推荐

• 二分查找：20 行代码里藏着的对数级智慧 — 更完整地讲二分的各种变体
• 插入、选择、冒泡排序（KU） — 排序也是分治，对照看 log 与 n log n
• 算法与问题求解入门（KU） — 复杂度记号的基础