---
title: 算法-查找与分治
aliases:
  - 查找与分治
  - 二分查找
  - Binary Search and Divide and Conquer
tags:
  - 计算机基础/算法
  - 类型/教程
created: 2026-10-11
updated: 2026-10-11
level: 入门
prerequisites:
  - "[[算法-复杂度分析]]"
  - "[[算法-排序]]"
sources:
  - https://oi-wiki.org/basic/binary/
  - https://oi-wiki.org/basic/divide-and-conquer/
  - https://oi-wiki.org/search/backtracking/
  - https://oi-wiki.org/math/quick-pow/
  - https://oi-wiki.org/basic/complexity/
  - https://cp-algorithms.com/num_methods/binary_search.html
  - https://cp-algorithms.com/num_methods/ternary_search.html
  - https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/
  - https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/
---

# 算法-查找与分治

> [!abstract] 这篇笔记讲什么
> 查找、分治、递归、回溯是四件互相咬合的事：**分治**是「把大问题切成同型小问题」的范式，**递归**是它的实现手段，**查找**（尤其是二分）是分治思想在有序数据上的极致简化，**回溯**则是递归在枚举问题上的暴力外壳。
> 读完你应该能：手写四种二分边界变体而不出错、识别「最小化最大值」型二分答案题、写出归并/快排的递推式、用回溯模板解决全排列/子集/组合总和/N 皇后，并说清记忆化搜索与动态规划的关系。

## 一、是什么：查找与分治分别解决什么问题

**查找（Search）**：在一组数据中定位满足某个条件的元素。若数据无序，只能顺序扫描；若数据**有序**，则可以用 $O(\log n)$ 的代价定位。

**分治（Divide and Conquer）**：把规模为 $n$ 的问题拆成若干个规模更小的**同型子问题**，分别求解后把结果**合并**，得到原问题的解。它的复杂度由递推式（recurrence）描述，例如：

$$
T(n) = 2T\left(\frac{n}{2}\right) + O(n) = O(n \log n)
$$

**递归（Recursion）** 是描述分治最自然的语言，也是回溯法的骨架；**记忆化搜索（Memoization）** 是把递归的重复子问题缓存起来，它和动态规划（Dynamic Programming, DP）本质上是同一件事的两种写法。

## 二、为什么需要它们 / 适用条件

| 技术 | 适用条件 | 不适用的情况 |
|---|---|---|
| 顺序查找 | 任何数据 | 数据量大且查询频繁时太慢 |
| 二分查找 | 数据**有序**（或存在单调判定函数），支持随机访问 | 链表等不支持 $O(1)$ 随机访问的结构；数据频繁插入删除 |
| 二分答案 | 答案空间**单调**（可行性关于答案是单调的） | 可行性不单调，或答案不是可枚举的数值区间 |
| 三分查找 | 函数在区间上是**严格单峰**（先减后增或先增后减） | 多峰函数、平台函数 |
| 分治 | 子问题同型且相互独立、合并代价可控 | 子问题重叠严重（此时应转向 DP） |
| 回溯 | 解可以表示成一步步的决策序列，且有明确的可行性判定 | 状态空间过大且没有强剪枝（应考虑 DP / 整数规划） |

> [!important] 一句话判断该不该用分治
> 如果「把问题切成两半后，左半的答案和右半的答案能拼出整体的答案，且跨界的代价是 $O(n)$ 级别」，就可以分治。归并排序能分治，是因为「两个有序数组合并」很快；最大子数组和也能分治，是因为跨越中点的最大和可以 $O(n)$ 扫出来。

## 三、核心内容

### 3.1 顺序查找与「有序性红利」

顺序查找就是逐个比较，平均比较次数 $\frac{n+1}{2}$，时间复杂度 $O(n)$。它看似没有优化空间，但如果数据**有序**，至少有三处可以改进：

```python
def sequential_search(a, target):
    """无序数组的顺序查找：最坏 O(n)"""
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1


def ordered_search(a, target):
    """有序数组的顺序查找：一旦当前元素已经大于 target 就可以收工"""
    for i, x in enumerate(a):
        if x == target:
            return i
        if x > target:          # 有序性带来的提前终止
            return -1
    return -1


def sentinel_search(a, target):
    """哨兵技巧：把 target 放到数组末尾，省掉每次循环的边界判断。
    注意：会修改原数组，用完必须还原（这里用切片副本演示，保持纯函数语义）。"""
    b = list(a) + [target]      # 末尾放哨兵，保证循环一定能停下来
    i = 0
    while b[i] != target:
        i += 1
    return i if i < len(a) else -1
```

| 优化手段 | 收益 | 代价 |
|---|---|---|
| 提前终止（有序性） | 未命中时平均只需扫一半 | 需要有序，维护有序本身要 $O(n)$ 或 $O(\log n)$ |
| 哨兵 | 每次迭代少一次下标越界判断，常数级提速 | 需要可写的额外空间，且要还原 |
| 二分 | 命中与未命中都是 $O(\log n)$ | 需要随机访问 + 有序 |

### 3.2 二分查找：三个前提与一个不变式

**前提**：① 数据有序（或存在单调的谓词）；② 支持 $O(1)$ 随机访问；③ 数据不频繁变动（否则维护有序的代价超过收益）。

**核心不变式（invariant）**：在循环的每一轮开始前，「答案一定落在当前区间内」。只要每轮都真正缩小了区间、且没有把可能的答案排除掉，正确性就有保证。写二分出错的根本原因几乎都是**不变式被破坏**，而不是「边界没调对」。

```python
def binary_search(a, target):
    """标准二分：返回任意一个等于 target 的下标，找不到返回 -1。
    循环不变式：答案（若存在）始终落在闭区间 [left, right] 内。"""
    left, right = 0, len(a) - 1
    while left <= right:                # 闭区间非空
        mid = left + (right - left) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            left = mid + 1              # mid 已排除，从 mid+1 开始
        else:
            right = mid - 1             # mid 已排除，到 mid-1 结束
    return -1
```

> [!note] 为什么要写 `mid = left + (right - left) // 2`
> 在 C/C++/Java 中，`(left + right) / 2` 在 `left + right` 超过 `int` 上限时会溢出成负数，导致数组越界。Python 的整数是任意精度、不会溢出，但把 `left + (right - left) // 2` 写成肌肉记忆可以避免换语言时踩坑。

### 3.3 四种边界变体（必须背下来）

真正在工程和面试中常用的不是「找一个等于」，而是下面这四种边界：

| 变体 | 中文叫法 | 语义 | 返回值范围 | 常用写法 |
|---|---|---|---|---|
| 第一个 $=$ | 查**第一个等于** | 最小的 $i$ 使 $a[i] = x$ | $[0, n-1]$ 或 $-1$ | 闭区间 `left <= right`，命中后继续往左压 |
| 最后一个 $=$ | 查**最后一个等于** | 最大的 $i$ 使 $a[i] = x$ | $[0, n-1]$ 或 $-1$ | 闭区间 `left <= right`，命中后继续往右压 |
| 第一个 $\ge$ | 查**第一个大于等于**（lower_bound） | 最小的 $i$ 使 $a[i] \ge x$ | $[0, n]$ | 左闭右开 `left < right` |
| 最后一个 $\le$ | 查**最后一个小于等于** | 最大的 $i$ 使 $a[i] \le x$ | $[-1, n-1]$ | 等于 `upper_bound - 1` |

```python
def first_equal(a, target):
    """第一个等于 target 的下标，不存在返回 -1"""
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if a[mid] < target:
            left = mid + 1
        else:                       # a[mid] >= target，mid 仍可能是答案
            right = mid - 1
    # 退出时 left 指向第一个 >= target 的位置
    return left if left < len(a) and a[left] == target else -1


def last_equal(a, target):
    """最后一个等于 target 的下标，不存在返回 -1"""
    left, right = 0, len(a) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if a[mid] <= target:        # a[mid] <= target，mid 仍可能是答案
            left = mid + 1
        else:
            right = mid - 1
    # 退出时 right 指向最后一个 <= target 的位置
    return right if right >= 0 and a[right] == target else -1


def lower_bound(a, target):
    """第一个 >= target 的下标；若全都小于 target 则返回 len(a)。
    采用左闭右开区间 [left, right)，好处是「没有答案」时天然由 right 表示。"""
    left, right = 0, len(a)
    while left < right:
        mid = left + (right - left) // 2
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid             # mid 可能是答案，区间右端收到 mid
    return left


def upper_bound(a, target):
    """第一个 > target 的下标；若全都不大于 target 则返回 len(a)"""
    left, right = 0, len(a)
    while left < right:
        mid = left + (right - left) // 2
        if a[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left


def last_le(a, target):
    """最后一个 <= target 的下标，不存在返回 -1（= upper_bound - 1）"""
    return upper_bound(a, target) - 1
```

**分步推演**：在 `a = [1, 2, 2, 2, 3, 5]` 上求 `first_equal(a, 2)` 与 `last_equal(a, 2)`：

| 轮次 | left | right | mid | a[mid] | 判定 | 新区间 |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 2 | $\ge 2$，right = mid-1 | [0, 1] |
| 2 | 0 | 1 | 0 | 1 | $< 2$，left = mid+1 | [1, 1] |
| 3 | 1 | 1 | 1 | 2 | $\ge 2$，right = mid-1 | [1, 0] 空 |
| 退出 | 1 | 0 | — | — | `a[1] == 2` | 返回 **1** |

`last_equal` 的轨迹则是 left 一路右移，最终 `right = 3`，`a[3] == 2`，返回 **3**。可见两个函数只差一个 `<` 与 `<=`，但退出时该看 `left` 还是 `right` 完全不同——记住这条口诀：**「压右边看 left，压左边看 right」**。

### 3.4 `left <= right` 与 `left < right` 两种写法的取舍

| 维度 | 闭区间 `while left <= right` | 左闭右开 `while left < right` |
|---|---|---|
| 区间表示 | $[left, right]$ | $[left, right)$ |
| 循环终止 | `left == right + 1`，区间为空 | `left == right`，区间剩一个元素 |
| 退出后含义 | `left` 是第一个满足「右压条件」的位置 | `left == right` 就是答案位置 |
| 是否需要额外判断 | 命中判定需要单独处理 | 通常无需再判断，直接返回 `left` |
| 出错倾向 | 容易忘记 `±1` 造成死循环 | 容易忘记 `right = len(a)` 而不是 `len(a)-1` |
| 推荐场景 | 「找一个等于」这类可以提前 return 的场景 | `lower_bound` / `upper_bound` / 二分答案 |

**统一心法**：不要背模板，而是每次写之前回答两个问题——① 我的区间是闭还是半开？② 当 `a[mid]` 满足条件时，答案可能在 `mid` 上还是在 `mid` 的某一侧？答案定了，`mid` 的取整方向也就定了。

### 3.5 死循环与越界陷阱

> [!warning] 三种经典死循环
> 1. **上取整缺失**：区间写成闭区间 `[left, right]`、循环条件 `left < right`，更新语句是 `left = mid`，而 `mid = (left + right) // 2` 向下取整。当 `right = left + 1` 时 `mid == left`，执行 `left = mid` 后区间不变 → 死循环。修法：改成 `mid = left + (right - left + 1) // 2`（上取整），或把更新改成 `left = mid + 1`。
> 2. **对称的另一半**：更新语句是 `right = mid`、`mid` 用上取整，同样会死循环。修法：`right = mid` 必须配下取整。
> 3. **更新语句没缩小搜索空间**：写成 `left = mid` / `right = mid` 却用了错误的取整方向；判据是「本轮区间长度必须严格小于上一轮」。
>
> 口诀：**`left = mid` 配上取整，`right = mid` 配下取整；只要出现 `mid ± 1`，取整方向随意。**

越界则主要来自两处：一是 `mid + 1` 后 `left` 可能等于 `len(a)`，之后若还访问 `a[left]` 就崩；二是 `right = mid - 1` 后可能等于 `-1`。**规则：循环退出后访问 `a[left]` / `a[right]` 之前，永远先做范围检查。**

### 3.6 二分答案：把「最优化」变成「判定」

**适用信号**：题目问「最小的最大值」「最大的最小值」「最少需要多少」「能否在 $k$ 步内完成」，且**可行性关于答案是单调的**——即若 $x$ 可行，则所有比 $x$ 更「宽松」的值也可行。

**套路四步**：
1. **确定答案范围** `[lo, hi]`：从题目约束推出上下界（不要图省事写 `0` 到 `10**18`，虽然也能过，但会掩盖越界 bug）。
2. **写判定函数** `feasible(x)`：给定候选答案 $x$，判断是否可行。它通常是一次 $O(n)$ 的贪心扫描。
3. **确定单调方向**：是「可行域在右边」（求最小可行值）还是「可行域在左边」（求最大可行值）。
4. **套模板**：求最小可行值用 `while lo < hi: mid=(lo+hi)//2; if feasible(mid): hi=mid else lo=mid+1`。

```python
def min_eating_speed(piles, h):
    """LeetCode 875 爱吃香蕉的珂珂：求最小速度 k，使总耗时 <= h。
    答案的单调性：速度越大耗时越少，所以「可行」是一个后缀区间。"""
    def feasible(k):
        # 每堆需要 ceil(p / k) 小时；k 越大总耗时越小
        return sum((p + k - 1) // k for p in piles) <= h

    lo, hi = 1, max(piles)          # 速度至少 1，超过最大堆也无意义
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                # mid 可行 → 答案不超过 mid
        else:
            lo = mid + 1            # mid 不可行 → 答案必须更大
    return lo


def split_array(nums, m):
    """LeetCode 410 分割数组的最大值：最小化「各段和的最大值」。
    这是「最小化最大值」的模板题，判定函数是一次贪心分段。"""
    def feasible(limit):
        cnt, cur = 1, 0             # 至少分成 1 段
        for x in nums:
            if cur + x > limit:     # 这一段装不下了，必须切一刀
                cnt += 1
                cur = x
            else:
                cur += x
            if cnt > m:
                return False
        return True

    lo, hi = max(nums), sum(nums)   # 下界：最大的单个元素；上界：不分段
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
```

**分步推演**：`nums = [7, 2, 5, 10, 8]`，`m = 2`。

| 轮次 | lo | hi | mid | feasible(mid) 的过程 | 结论 |
|---|---|---|---|---|---|
| 1 | 10 | 32 | 21 | 7+2+5=14，+10=24>21 切；10+8=18 一段，共 2 段 | 可行，hi = 21 |
| 2 | 10 | 21 | 15 | 7+2+5=14，+10>15 切；10+8=18>15 切 → 3 段 | 不可行，lo = 16 |
| 3 | 16 | 21 | 18 | 7+2+5=14，+10>18 切；10+8=18 一段 | 可行，hi = 18 |
| 4 | 16 | 18 | 17 | 同上，10+8=18>17 切 → 3 段 | 不可行，lo = 18 |
| 退出 | 18 | 18 | — | — | 答案 **18** |

### 3.7 插值查找与斐波那契查找

**插值查找（Interpolation Search）** 的核心想法：如果数据是**近似均匀分布**的，那么可以用数值比例去猜位置，而不是死板地取中点。

$$
mid = left + \frac{x - a[left]}{a[right] - a[left]} \cdot (right - left)
$$

**斐波那契查找（Fibonacci Search）** 用斐波那契数列 $F_k$ 代替折半：它把所有比较都变成**加减法**（在早期硬件上比除法便宜），且当 `mid` 落在数组外时只需单向收缩，几乎不需要额外边界判断。

```python
def interpolation_search(a, target):
    """插值查找：均匀分布时接近 O(log log n)，最坏 O(n)"""
    lo, hi = 0, len(a) - 1
    while lo <= hi and a[lo] <= target <= a[hi]:
        if a[hi] == a[lo]:
            break                       # 区间内数值相同，无法按比例定位
        pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])
        if a[pos] == target:
            return pos
        if a[pos] < target:
            lo = pos + 1
        else:
            hi = pos - 1
    if lo < len(a) and a[lo] == target:
        return lo
    return -1


def fibonacci_search(a, target):
    """斐波那契查找。要求 a 升序。
    思路：用 F[k] 作为区间长度的上界，用 F[k-1]、F[k-2] 划分左右子区间。"""
    n = len(a)
    if n == 0:
        return -1
    fib_mm2, fib_mm1 = 0, 1             # F[k-2], F[k-1]
    fib_m = fib_mm2 + fib_mm1           # F[k]
    while fib_m < n:                    # 找到最小的 F[k] >= n
        fib_mm2, fib_mm1 = fib_mm1, fib_m
        fib_m = fib_mm1 + fib_mm2

    offset = -1                         # 已确认排除的左边界
    while fib_m > 1:
        i = min(offset + fib_mm2, n - 1)    # 关键：越界时夹到 n-1
        if a[i] < target:
            fib_m, fib_mm1 = fib_mm1, fib_mm2       # 左半丢弃，整体左移
            fib_mm2 = fib_m - fib_mm1
            offset = i
        elif a[i] > target:
            fib_m, fib_mm1 = fib_mm2, fib_mm1 - fib_mm2
            fib_mm2 = fib_m - fib_mm1
        else:
            return i
    if fib_mm1 and offset + 1 < n and a[offset + 1] == target:
        return offset + 1
    return -1
```

| 查找方法 | 时间复杂度（平均） | 最坏 | 前提 | 备注 |
|---|---|---|---|---|
| 顺序查找 | $O(n)$ | $O(n)$ | 无 | 无需有序 |
| 二分查找 | $O(\log n)$ | $O(\log n)$ | 有序 + 随机访问 | 通用首选 |
| 插值查找 | $O(\log \log n)$ | $O(n)$ | 有序 + **近似均匀分布** | 分布倾斜时退化 |
| 斐波那契查找 | $O(\log n)$ | $O(\log n)$ | 有序 + 随机访问 | 常数项小，只做加减法 |

### 3.8 三分查找：求单峰函数的极值

若 $f$ 在区间上**严格单峰**，可以每次取两个三分点 $m_1 < m_2$，比较 $f(m_1)$ 与 $f(m_2)$：

- 若 $f(m_1) < f(m_2)$：极值不可能在 $[l, m_1]$，令 $l = m_1$（对单峰「谷」则相反）；
- 若 $f(m_1) > f(m_2)$：极值不可能在 $[m_2, r]$，令 $r = m_2$。

实数域三分迭代 $O(\log_{1.5} \frac{r-l}{\varepsilon})$ 次即可达到精度 $\varepsilon$；整数域三分要小心平台（相等的连续段），此时改比较相邻点更稳。

```python
def ternary_search_max(f, lo, hi, eps=1e-9):
    """求单峰函数 f 在 [lo, hi] 上的最大值点（浮点三分）"""
    while hi - lo > eps:
        m1 = lo + (hi - lo) / 3         # 左三分点
        m2 = hi - (hi - lo) / 3         # 右三分点
        if f(m1) < f(m2):               # 峰值在 m1 右侧
            lo = m1
        else:                           # 峰值在 m2 左侧
            hi = m2
    return (lo + hi) / 2


def ternary_search_int(f, lo, hi):
    """整数域单峰求最大值点，退出条件用 hi - lo > 2 以避免平台死循环"""
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if f(m1) < f(m2):
            lo = m1 + 1
        else:
            hi = m2 - 1
    return max(range(lo, hi + 1), key=f)
```

> [!warning] 三分查找的常见误用
> 三分只对**严格单峰**函数有效。遇到多峰函数（例如 `f(i) = 山峰数组的多个峰值`）三分会收敛到局部最优；遇到长平台区（`f` 在很长一段取值相同）整数三分可能不收缩。此时应改用「二分导数符号」或直接二分答案。

### 3.9 分治范式：分—治—合

分治三步（分-治-合，Divide-Conquer-Combine）：

1. **分（Divide）**：把规模 $n$ 的问题拆成 $a$ 个规模 $n/b$ 的子问题；
2. **治（Conquer）**：递归求解子问题，直到规模小到可以直接算出（base case）；
3. **合（Combine）**：把子问题的解合并成原问题的解。

复杂度由递推式给出：

$$
T(n) = a\,T\left(\frac{n}{b}\right) + f(n)
$$

由主定理（Master Theorem），令 $c = \log_b a$：

$$
T(n) = \begin{cases}
\Theta(n^{c}) & f(n) = O(n^{c-\varepsilon}) \\
\Theta(n^{c}\log n) & f(n) = \Theta(n^{c}) \\
\Theta(f(n)) & f(n) = \Omega(n^{c+\varepsilon}) \text{ 且满足正则条件}
\end{cases}
$$

**归并排序（Merge Sort）**：分成两半，各自排好，再线性合并。

$$
T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) \;\Rightarrow\; a = 2,\; b = 2,\; c = 1,\; f(n) = \Theta(n) \;\Rightarrow\; T(n) = \Theta(n\log n)
$$

**快速排序（Quick Sort）**：按枢轴（pivot）划分成两段，两段各自排好即可，不需要合并。最好情况每次均分：

$$
T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) = \Theta(n\log n)
$$

最坏情况每次只分出一个元素（例如对已排序数组取首元素做枢轴）：

$$
T(n) = T(n-1) + \Theta(n) = \Theta(n^2)
$$

```python
def merge_sort(a):
    """归并排序：分治的教科书范例，稳定，O(n log n)"""
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])          # 治：递归排好左半
    right = merge_sort(a[mid:])         # 治：递归排好右半
    # 合：线性合并两个有序数组
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:         # <= 保证稳定性
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


from random import randint

def quick_sort(a):
    """快速排序：随机枢轴避免最坏情况，平均 O(n log n)"""
    if len(a) <= 1:
        return a
    p = a[randint(0, len(a) - 1)]       # 随机选枢轴，抵御有序输入的退化
    less = [x for x in a if x < p]
    equal = [x for x in a if x == p]    # 三路划分：大量重复元素时更快
    greater = [x for x in a if x > p]
    return quick_sort(less) + equal + quick_sort(greater)
```

> [!note] 快速排序为什么不需要「合」
> 合并的代价是分治复杂度的关键项。归并排序因为「合」要 $O(n)$，所以递推式里必须带上它；快排的「合」是 $O(1)$（两段已经就位，直接拼接），代价被隐藏在「分」里——这解释了为什么快排的瓶颈是划分质量而不是合并。

### 3.10 分治经典应用

#### （1）大整数乘法（Karatsuba）

朴素竖式乘法把两个 $n$ 位整数相乘需要 $O(n^2)$。Karatsuba 把每个数拆成高低两半 $x = a\cdot B^{m} + b$、$y = c\cdot B^{m} + d$，则

$$
xy = ac\cdot B^{2m} + (ad + bc)\cdot B^{m} + bd
$$

朴素的做法需要 4 次子乘法（$ac$、$ad$、$bc$、$bd$）；Karatsuba 用一次额外加减换掉一次乘法：

$$
ad + bc = (a+b)(c+d) - ac - bd
$$

于是只需 3 次子乘法：

$$
T(n) = 3T\left(\frac{n}{2}\right) + O(n) \;\Rightarrow\; T(n) = O\left(n^{\log_2 3}\right) \approx O\left(n^{1.585}\right)
$$

```python
def karatsuba(x, y):
    """大整数乘法：T(n) = 3T(n/2) + O(n) = O(n^1.585)"""
    if x < 10 or y < 10:                        # base case：个位数直接乘
        return x * y
    n = max(len(str(x)), len(str(y)))
    half = n // 2
    base = 10 ** half
    a, b = divmod(x, base)                      # x = a * base + b
    c, d = divmod(y, base)                      # y = c * base + d
    z0 = karatsuba(b, d)                        # bd
    z2 = karatsuba(a, c)                        # ac
    # (a+b)(c+d) - ac - bd = ad + bc，只花一次乘法
    z1 = karatsuba(a + b, c + d) - z2 - z0
    return z2 * (base * base) + z1 * base + z0


def naive_multiply(x, y):
    """对照用的朴素乘法（竖式），O(n^2)"""
    return x * y            # Python 内置的大整数乘法已优于 Karatsuba
```

> [!note] 为什么工程中不用手写 Karatsuba
> CPython 对超大整数使用 Karatsuba 算法（阈值约 70 位，见 CPython 源码 `longobject.c`），更大的数还会切换到 Toom-Cook。这里手写是为了理解分治如何把 $O(n^2)$ 降到 $O(n^{1.585})$，实际项目中请直接用语言内置的大整数。

#### （2）最近点对（Closest Pair of Points）

暴力枚举所有点对是 $O(n^2)$。分治做法：按 $x$ 排序后从中线切成左右两半，递归求出左右两半的最近距离 $d$；**再把中线两侧宽度为 $d$ 的「条带（strip）」内的点按 $y$ 排序，只需检查每个点后面的常数个（≤ 7）点**。

$$
T(n) = 2T\left(\frac{n}{2}\right) + O(n) = O(n\log n)
$$

```python
def closest_pair(points):
    """最近点对：返回最近距离的平方（避免浮点开方误差）。
    要求至少有 2 个点。复杂度 O(n log n)。"""
    if len(points) < 2:
        raise ValueError("至少需要 2 个点")

    def dist2(p, q):
        return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2

    def solve(px, py):
        n = len(px)
        if n <= 3:                              # base case：暴力，常数小
            return min(dist2(px[i], px[j])
                       for i in range(n) for j in range(i + 1, n))
        mid = n // 2
        mid_x = px[mid][0]
        left_set = set(px[:mid])
        # 保持 py 的 y 有序性，按 x 的中线切分（这一步是 O(n)）
        ly = [p for p in py if p in left_set]
        ry = [p for p in py if p not in left_set]
        d = min(solve(px[:mid], ly), solve(px[mid:], ry))
        # 只留下离中线小于 d 的点；按 y 序扫描时每个点最多比较后面 7 个
        strip = [p for p in py if (p[0] - mid_x) ** 2 < d]
        for i in range(len(strip)):
            for j in range(i + 1, min(i + 8, len(strip))):
                if (strip[j][1] - strip[i][1]) ** 2 >= d:
                    break                       # y 序保证：再往后只会更远
                d = min(d, dist2(strip[i], strip[j]))
        return d

    px = sorted(points)
    return solve(px, sorted(px, key=lambda p: p[1]))
```

#### （3）逆序对计数（Counting Inversions）

> 在数组 $a$ 中，若 $i < j$ 且 $a[i] > a[j]$，则称 $(i, j)$ 是一个**逆序对（inversion）**。逆序对数量既可用于衡量序列的「无序程度」，也是排序算法交换次数的下界。

分治做法就是归并排序：**在合并两个有序子数组时，一旦决定从右半取元素，说明它小于左半剩下的所有元素，一次性产生 `len(left) - i` 个跨区间逆序对。**

```python
def count_inversions(a):
    """逆序对计数：返回 (升序数组, 逆序对个数)，O(n log n)"""
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cl = count_inversions(a[:mid])        # 左半内部的逆序对
    right, cr = count_inversions(a[mid:])       # 右半内部的逆序对
    merged, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            # right[j] 比 left[i:] 全部元素都小 → 一次产生 len(left)-i 个逆序对
            cross += len(left) - i
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, cl + cr + cross
```

**分步推演**：`a = [2, 4, 1, 3]`。

| 步骤 | 子数组 | 结果 |
|---|---|---|
| 分 | `[2,4]` \| `[1,3]` | — |
| 治左 | `[2]`,`[4]` 合并 | 无逆序，`[2,4]`，跨区间 0 |
| 治右 | `[1]`,`[3]` 合并 | 无逆序，`[1,3]`，跨区间 0 |
| 合 | `[2,4]` 与 `[1,3]` | 取 1（`4-0=2` 个）、取 2（`4-1=1`… 实际取 1 时 i=0 → 2 个；取 2 时 j=1，`left[0]=2 <= 3` 取左） |

最终 `cross = 2`（即 $(2,1)$、$(4,1)$），加左右各 0，答案 **2**。

#### （4）快速幂（Fast Exponentiation）

计算 $a^n$ 时，若 $n$ 为偶数则 $a^n = (a^{n/2})^2$，若为奇数则 $a^n = a\cdot a^{n-1}$：

$$
T(n) = T\left(\frac{n}{2}\right) + O(1) = O(\log n)
$$

```python
def fast_pow(base, exp, mod=None):
    """快速幂（迭代版）。mod 为 None 时不取模。O(log exp)"""
    result = 1
    if mod:
        base %= mod
    while exp > 0:
        if exp & 1:                             # 当前二进制位为 1
            result = result * base % mod if mod else result * base
        base = base * base % mod if mod else base * base
        exp >>= 1                               # 指数右移一位
    return result


def mat_mul(A, B, mod):
    """2x2 矩阵乘法（用于矩阵快速幂）"""
    return [[sum(A[i][k] * B[k][j] for k in range(2)) % mod for j in range(2)]
            for i in range(2)]


def fib_matrix(n, mod=10 ** 9 + 7):
    """矩阵快速幂求第 n 项斐波那契数，O(log n)。
    原理：[F(n+1), F(n); F(n), F(n-1)] = [[1,1],[1,0]]^n"""
    result = [[1, 0], [0, 1]]                   # 单位矩阵
    power = [[1, 1], [1, 0]]
    while n > 0:
        if n & 1:
            result = mat_mul(result, power, mod)
        power = mat_mul(power, power, mod)
        n >>= 1
    return result[0][1]
```

### 3.11 递归的本质与递归树

**递归（Recursion）** 是把问题交给「规模更小的同一个函数」来解。一个正确的递归必须有两个要素：

1. **基准情形（base case）**：规模小到可以直接给出答案，否则会无限递归；
2. **递归关系（recursive case）**：每次调用必须让问题**严格变小**，且子问题的解能拼出原问题的解。

**递归树（recursion tree）** 是把递归调用画成树，用来估算复杂度：树高 × 每层的工作量。以 $T(n) = 2T(n/2) + cn$ 为例：

| 层 | 节点数 | 每节点代价 | 该层总代价 |
|---|---|---|---|
| 0 | $1$ | $cn$ | $cn$ |
| 1 | $2$ | $cn/2$ | $cn$ |
| 2 | $4$ | $cn/4$ | $cn$ |
| … | … | … | … |
| $\log_2 n$ | $n$ | $c$ | $cn$ |

共 $\log_2 n + 1$ 层，每层 $cn$，总计 $O(n\log n)$ —— 与主定理结论一致。

> [!warning] Python 递归深度
> CPython 默认递归深度上限约 1000 层（`sys.getrecursionlimit()`）。递归深度为 $O(n)$ 的写法（如快排最坏情况、链表递归反转）在 $n$ 较大时会抛 `RecursionError`。工程做法：改成显式栈的迭代版本，或谨慎调大 `sys.setrecursionlimit`（调大后仍可能因 C 栈溢出而崩溃）。

### 3.12 回溯法（Backtracking）

回溯是「带撤销的深度优先搜索」：把求解过程看作一系列决策，每一步尝试一个候选值，走不通就**撤销**回到上一步换一个候选值。它枚举的是**决策树**，因此复杂度通常是指数级——所以**剪枝（pruning）是回溯的灵魂**。

**通用模板**：

```python
def backtrack(state):
    if is_complete(state):          # 1. 到达叶子：记录一个解
        record(state)
        return
    for choice in candidates(state):    # 2. 枚举本层的所有候选
        if not is_valid(choice, state): # 3. 剪枝：不合法的分支直接砍掉
            continue
        apply(choice, state)            # 4. 做选择
        backtrack(state)                # 5. 递归进入下一层
        undo(choice, state)             # 6. 撤销选择（回溯的关键）
```

**（1）全排列**——用 `used` 数组标记已选元素，避免同一元素被重复使用。

```python
def permute(nums):
    """LeetCode 46 全排列。时间 O(n * n!)，空间 O(n)"""
    res, path = [], []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            res.append(path[:])                 # 必须拷贝，path 会被继续修改
            return
        for i, x in enumerate(nums):
            if used[i]:                         # 剪枝：已用过的数字不能再选
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()                          # 撤销
            used[i] = False

    dfs()
    return res
```

**（2）子集**——用 `start` 参数保证「只往后选」，从而天然避免 `[1,2]` 与 `[2,1]` 这类重复。

```python
def subsets(nums):
    """LeetCode 78 子集。每个递归节点都是一个合法子集，共 2^n 个"""
    res, path = [], []

    def dfs(start):
        res.append(path[:])                     # 进入节点即收集（含空集）
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)                          # 只能选下标更大的元素
            path.pop()

    dfs(0)
    return res


def subsets_with_dup(nums):
    """LeetCode 90 子集 II：先排序，再在同层跳过重复元素"""
    nums = sorted(nums)
    res, path = [], []

    def dfs(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                        # 同层去重：相同值的分支只走第一支
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return res
```

**（3）组合总和**——排序 + `break` 剪枝，是「可行性剪枝」的典型。

```python
def combination_sum(candidates, target):
    """LeetCode 39 组合总和：每个数可重复使用，求所有和为 target 的组合"""
    cand = sorted(candidates)                   # 排序是 break 剪枝的前提
    res, path = [], []

    def dfs(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(cand)):
            if cand[i] > remain:                # 剪枝：后面的只会更大，全部无解
                break
            path.append(cand[i])
            dfs(i, remain - cand[i])            # 传 i（不是 i+1）：允许重复取自己
            path.pop()

    dfs(0, target)
    return res
```

**（4）N 皇后**——用位运算集合 $O(1)$ 判断冲突，是最经典的强剪枝示例。

```python
def solve_n_queens(n):
    """LeetCode 51 N 皇后：返回所有解（每个解是 n 个字符串的列表）"""
    res = []
    board = [["."] * n for _ in range(n)]

    def dfs(row, cols, diag1, diag2):
        if row == n:
            res.append(["".join(r) for r in board])
            return
        # 三位掩码取并集的补集 = 本行所有不冲突的列
        avail = ~(cols | diag1 | diag2) & ((1 << n) - 1)
        while avail:
            bit = avail & (-avail)              # 取最低位的 1（lowbit）
            avail -= bit
            col = bit.bit_length() - 1
            board[row][col] = "Q"
            # 主对角线往左下移一位，副对角线往右下移一位
            dfs(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1)
            board[row][col] = "."

    dfs(0, 0, 0, 0)
    return res
```

**剪枝技巧总结**：

| 剪枝类型 | 思路 | 例子 |
|---|---|---|
| 可行性剪枝 | 当前部分解已经不可能满足约束 | 组合总和中 `cand[i] > remain` 就 `break` |
| 最优性剪枝 | 当前代价已不优于已知最优解 | 旅行商问题中「当前路径长度 ≥ 已有最优」 |
| 搜索顺序剪枝 | 先试更可能成功的分支 | 排序后从大到小试、先放约束最多的变量 |
| 对称性剪枝 | 破掉等价解 | N 皇后只搜第一行左半边；子集用 `start` 保证有序 |
| 同层去重 | 同一层相同值只走一次 | 子集 II 的 `nums[i] == nums[i-1]` 判断 |
| 记忆化剪枝 | 缓存「从该状态出发」的结论 | 记忆化搜索（见 3.13） |

### 3.13 记忆化搜索与动态规划的关系

**记忆化搜索（Memoization）**：保留递归的「自顶向下」写法，但把每个状态的答案缓存起来，第二次遇到直接返回。**它和递推式 DP 是同一套状态与转移方程的两种实现**，区别只在遍历顺序和是否显式建表。

```python
from functools import lru_cache

def fib_memo(n):
    """自顶向下：记忆化搜索，只有被用到的状态才被计算"""
    @lru_cache(maxsize=None)
    def f(k):
        if k <= 1:
            return k                            # base case
        return f(k - 1) + f(k - 2)
    return f(n)


def fib_iter(n):
    """自底向上：递推 + 滚动变量，空间 O(1)"""
    if n <= 1:
        return n
    prev, cur = 0, 1
    for _ in range(2, n + 1):
        prev, cur = cur, prev + cur
    return cur
```

| 维度 | 记忆化搜索（自顶向下） | 递推 DP（自底向上） |
|---|---|---|
| 写法 | 递归 + 缓存 | 循环填表 |
| 状态访问 | 只算**真正需要**的状态 | 通常要枚举全部状态 |
| 递归深度 | 受栈深限制（可能 `RecursionError`） | 无栈风险 |
| 空间优化 | 难做滚动数组 | 易做滚动数组 / 维度压缩 |
| 边界处理 | 写在 base case 里，直观 | 需要手动初始化 |
| 适用场景 | 状态转移有大量「不可达」分支、拓扑序不明显 | 状态空间规则、需要极致常数与空间 |

> [!tip] 怎么选
> 先写记忆化搜索把状态与转移确认正确，**再**改写成递推版做空间优化——这是竞赛和面试里最稳的路径。若状态之间存在环（转移互相依赖），记忆化搜索会死循环，此时必须找到拓扑序或用高斯消元等特殊手段。

### 3.14 三大范式选型对比

| 维度 | 二分 / 二分答案 | 分治 | 回溯 |
|---|---|---|---|
| 解决的问题 | 有序查找、单调最优化 | 可切分且可合并的问题 | 枚举所有可行解 / 判定存在性 |
| 复杂度 | $O(\log n)$ / $O(n\log V)$ | 由递推式决定，常见 $O(n\log n)$ | 指数级，靠剪枝降常数 |
| 关键前提 | 单调性 | 子问题独立 + 合并代价可控 | 决策可表示 + 可剪枝 |
| 典型题 | 搜索插入位置、分割数组的最大值 | 归并排序、逆序对、最近点对 | 全排列、子集、N 皇后 |
| 是否用递归 | 通常迭代 | 通常递归 | 必然递归 |
| 可否转 DP | — | 子问题重叠时应转 DP | 有重叠子问题时加记忆化即可 |

## 四、注意事项与常见坑

> [!warning] 什么时候不能用这些方法
> - **数据无序且查询次数很少**：为了二分先排序是 $O(n\log n)$，不如直接顺序查找 $O(n)$。二分的收益只有在「一次排序、多次查询」时才体现。
> - **数据结构不支持随机访问**：链表上「二分」没有意义——定位中点本身就要 $O(n)$，总复杂度退化到 $O(n)$。请改用跳表、平衡树等结构。
> - **判定函数不单调**：二分答案的前提是「$x$ 可行 ⇒ 所有更大的 $x$ 也可行」（或反向）。若可行性忽真忽假，二分会返回一个无意义的结果且**不会报错**——这是最难发现的 bug，务必先用小数据暴力验证单调性。
> - **函数非单峰**：三分查找对多峰函数只能收敛到局部极值。
> - **递归深度与 $n$ 同阶**：改用迭代或显式栈。
> - **子问题重叠严重**：分治会做重复计算，应改成动态规划（例如「斐波那契」用分治递归是 $O(2^n)$，用 DP 是 $O(n)$）。

> [!warning] 其他高频坑
> 1. **`mid` 取整方向与更新语句不匹配**导致死循环（见 3.5）。
> 2. **循环退出后直接访问 `a[left]`** 导致越界，忘记判断 `left < len(a)`。
> 3. **`feasible` 函数写了 $O(n^2)$**，使二分答案整体退化；判定函数必须尽量线性。
> 4. **二分答案的初始上下界没覆盖真实答案**：例如「速度至少为 1」写成 `0`，会触发除零。
> 5. **回溯忘记撤销状态**，导致后续分支读到脏数据——这类 bug 的表现是「答案偏少」，而不是报错。
> 6. **回溯记录答案时没有拷贝** `path[:]`，最终所有解都指向同一个被清空的列表。
> 7. **归并排序中用了 `<` 而不是 `<=`**，破坏稳定性；逆序对计数中用了 `<=` 又会漏算相等的逆序对（相等不算逆序对，所以必须写 `<=` 取左边）。
> 8. **`lru_cache` 的参数必须可哈希**：传 `list` 会报 `TypeError`，需要转成 `tuple`。

## 五、练习题

### 练习 1（二分变体，给出完整解题过程）

> **LeetCode 33 搜索旋转排序数组**：整数数组 `nums` 按升序排列后在某处旋转（例如 `[0,1,2,4,5,6,7]` 变成 `[4,5,6,7,0,1,2]`）。请以 $O(\log n)$ 找出 `target` 的下标，不存在返回 `-1`。数组中无重复元素。

**第一步：分析结构**。旋转后数组被分成两段升序区间。取 `mid` 后，`[left, mid]` 与 `[mid, right]` 中**必有一段是完全有序的**（因为旋转点只有一个）。这是我们可以继续二分的依据。

**第二步：写出判定逻辑**。若 `a[left] <= a[mid]`，说明左半段有序：此时若 `a[left] <= target < a[mid]`，答案必在左半，否则在右半。反之右半段有序，对称处理。

**第三步：实现**。

```python
def search_rotated(nums, target):
    """LeetCode 33：旋转有序数组二分查找，O(log n)"""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            # 左半段 [left, mid] 有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # 右半段 [mid, right] 有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
```

**第四步：分步推演**。`nums = [4, 5, 6, 7, 0, 1, 2]`，`target = 0`：

| 轮次 | left | right | mid | nums[mid] | 哪半有序 | 判定 | 新区间 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 左半 `[4..7]` 有序 | `4 <= 0 < 7` 为假 | [4, 6] |
| 2 | 4 | 6 | 5 | 1 | 左半 `[0,1]` 有序 | `0 <= 0 < 1` 为真 | [4, 4] |
| 3 | 4 | 4 | 4 | 0 | — | 命中 | 返回 **4** |

**第五步：边界检查**。`nums` 为空 → `right = -1`，循环不进入，返回 `-1`。数组未旋转（完全升序）→ 走「左半有序」分支，退化成标准二分，仍然正确。含重复元素时该判定失效（`nums[left] == nums[mid]` 无法判断哪边有序），需要改成「先收缩相等边界」，复杂度退化为 $O(n)$ 最坏。

### 练习 2（二分答案）

> **LeetCode 875 爱吃香蕉的珂珂**：`piles[i]` 表示第 $i$ 堆香蕉的数量，警卫将在 $h$ 小时后回来。珂珂每小时选择一堆吃掉 $k$ 根（不足 $k$ 根就吃完这堆并停止本小时），求能在 $h$ 小时内吃完的最小 $k$。

提示：判定函数为 `sum(ceil(p / k) for p in piles) <= h`，它关于 $k$ 单调不增。答案区间是 $[1, \max(piles)]$。

### 练习 3（分治）

> **LeetCode 493 翻转对**（或《剑指 Offer》51 数组中的逆序对）：统计满足 $i < j$ 且 $a[i] > 2 \cdot a[j]$ 的数对个数，要求 $O(n\log n)$。

提示：把「归并时右半元素小于左半剩余全部元素」的计数条件由 `a[i] > a[j]` 改成 `a[i] > 2 * a[j]`；注意计数与合并必须分成两个独立循环，不能边合并边计数（因为 `2 * a[j]` 的判定不满足归并的单调合并顺序）。

### 练习 4（回溯 + 剪枝）

> **LeetCode 22 括号生成**：给出 $n$ 对括号的所有合法组合。

提示：用 `open`、`close` 两个计数器剪枝——`open < n` 才能放左括号，`close < open` 才能放右括号。这两条剪枝直接把 $2^{2n}$ 的枚举压到卡特兰数 $\frac{1}{n+1}\binom{2n}{n}$。

### 练习 5（三分查找）

> 已知 $f(x)$ 在 $[0, 100]$ 上先增后减，$f$ 只能通过一次函数调用求值，求最大值点，误差不超过 $10^{-6}$。

提示：直接用 3.8 节的 `ternary_search_max`，迭代约 $\log_{1.5}(10^8) \approx 46$ 次；若 $f$ 可导，改为对导数二分会更快。

## 六、常见问题 FAQ

> [!question] 为什么 Python 的 `bisect` 模块只提供了 `bisect_left` 和 `bisect_right`，没有「查找等于」？
> 因为「第一个 $\ge x$」和「第一个 $> x$」是更基础的**位置**语义：`bisect_left(a, x)` 就是 `lower_bound`；判断是否命中只需 `i = bisect_left(a, x); i < len(a) and a[i] == x`。「等于」可以由它们组合得到，反过来则不行。这也解释了为什么工程代码里 `lower_bound` 比「找等于」更常用。

> [!question] 二分查找用递归写和用迭代写有区别吗？
> 结果是相同的，复杂度也是相同的 $O(\log n)$，但递归版每次调用有函数调用开销且占用栈空间（深度 $O(\log n)$，通常无风险）。**工程上优先迭代**：常数更小、没有 `RecursionError` 风险、便于编译器优化。

> [!question] 分治和动态规划到底怎么区分？
> 关键看**子问题是否重叠**。分治假设子问题相互独立（归并排序里左半和右半互不影响），重复计算不存在；DP 专门处理子问题重叠的情况，用表格或缓存复用结果。判定方法：画出递归树，若不同分支出现相同参数，就应该用 DP。

> [!question] 回溯的时间复杂度怎么估？
> 数决策树的节点数。全排列是 $O(n \cdot n!)$（$n!$ 个叶子，每个叶子拷贝长度为 $n$ 的解）；子集是 $O(n \cdot 2^n)$（$2^n$ 个节点）；N 皇后在最坏情况下是 $O(n!)$，但位运算剪枝让实际访问的节点数远小于此。**面试时给出「决策树大小 × 每个节点的工作量」即可**，不必给出紧确界。

## 相关笔记

- [[算法-复杂度分析]]：主定理与递归树估算法是本文递推式分析的基础
- [[算法-排序]]：归并排序与快速排序既是分治的范例，也是理解递推式的入口
- [[算法-动态规划与贪心]]：记忆化搜索是通往 DP 五步法的桥梁
- [[数据结构-树与堆]]：递归树、树的遍历与 N 皇后的搜索结构都依赖树的直觉
- [[工具-07-调试技巧]]：二分定位 bug（binary search debugging）正是二分思想在调试中的应用
- [[00-索引]] / [[学习路线图]]：回到总导航安排学习顺序

## 参考来源

- [OI Wiki · 二分](https://oi-wiki.org/basic/binary/)：二分查找、二分答案与三分查找的中文系统讲解
- [OI Wiki · 分治](https://oi-wiki.org/basic/divide-and-conquer/)：分治范式与经典分治问题
- [OI Wiki · 回溯法](https://oi-wiki.org/search/backtracking/)：回溯模板与剪枝技巧
- [OI Wiki · 快速幂](https://oi-wiki.org/math/quick-pow/)：快速幂与矩阵快速幂
- [OI Wiki · 复杂度](https://oi-wiki.org/basic/complexity/)：主定理与递归式复杂度
- [cp-algorithms · Binary Search](https://cp-algorithms.com/num_methods/binary_search.html)：二分的边界处理与实现细节
- [cp-algorithms · Ternary Search](https://cp-algorithms.com/num_methods/ternary_search.html)：三分查找的正确性与整数实现
- [GeeksforGeeks · Closest Pair of Points](https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/)：最近点对条带内的常数比较界
- [MIT OCW 6.006 Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)：分治、递归树与主定理的公开课
- [LeetCode 33 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/) · [34 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/) · [410 分割数组的最大值](https://leetcode.cn/problems/split-array-largest-sum/) · [875 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/) · [51 N 皇后](https://leetcode.cn/problems/n-queens/) · [78 子集](https://leetcode.cn/problems/subsets/) · [39 组合总和](https://leetcode.cn/problems/combination-sum/)

