w wyl123ly 的博客
MD

算法-查找与分治

47 KB 2026.10.11 原文件

算法-查找与分治

这篇笔记讲什么

查找、分治、递归、回溯是四件互相咬合的事:分治是「把大问题切成同型小问题」的范式,递归是它的实现手段,查找(尤其是二分)是分治思想在有序数据上的极致简化,回溯则是递归在枚举问题上的暴力外壳。

读完你应该能:手写四种二分边界变体而不出错、识别「最小化最大值」型二分答案题、写出归并/快排的递推式、用回溯模板解决全排列/子集/组合总和/N 皇后,并说清记忆化搜索与动态规划的关系。

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

查找(Search):在一组数据中定位满足某个条件的元素。若数据无序,只能顺序扫描;若数据有序,则可以用 的代价定位。

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

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

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

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

一句话判断该不该用分治

如果「把问题切成两半后,左半的答案和右半的答案能拼出整体的答案,且跨界的代价是 级别」,就可以分治。归并排序能分治,是因为「两个有序数组合并」很快;最大子数组和也能分治,是因为跨越中点的最大和可以 扫出来。

三、核心内容

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

顺序查找就是逐个比较,平均比较次数 ,时间复杂度 。它看似没有优化空间,但如果数据有序,至少有三处可以改进:

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

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

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

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

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

为什么要写 mid = left + (right - left) // 2

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

3.3 四种边界变体(必须背下来)

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

变体中文叫法语义返回值范围常用写法
第一个 查第一个等于最小的 使 或 闭区间 left <= right,命中后继续往左压
最后一个 查最后一个等于最大的 使 或 闭区间 left <= right,命中后继续往右压
第一个 查第一个大于等于(lower_bound)最小的 使 左闭右开 left < right
最后一个 查最后一个小于等于最大的 使 等于 upper_bound - 1
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):

轮次leftrightmida[mid]判定新区间
10522,right = mid-1[0, 1]
20101,left = mid+1[1, 1]
31112,right = mid-1[1, 0] 空
退出10——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 + 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 死循环与越界陷阱

三种经典死循环

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 二分答案:把「最优化」变成「判定」

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

套路四步:

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

轮次lohimidfeasible(mid) 的过程结论
11032217+2+5=14,+10=24>21 切;10+8=18 一段,共 2 段可行,hi = 21
21021157+2+5=14,+10>15 切;10+8=18>15 切 → 3 段不可行,lo = 16
31621187+2+5=14,+10>18 切;10+8=18 一段可行,hi = 18
4161817同上,10+8=18>17 切 → 3 段不可行,lo = 18
退出1818——答案 18

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

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

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

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
查找方法时间复杂度(平均)最坏前提备注
顺序查找无无需有序
二分查找有序 + 随机访问通用首选
插值查找有序 + 近似均匀分布分布倾斜时退化
斐波那契查找有序 + 随机访问常数项小,只做加减法

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

若 在区间上严格单峰,可以每次取两个三分点 ,比较 与 :

  • 若 :极值不可能在 ,令 (对单峰「谷」则相反);
  • 若 :极值不可能在 ,令 。

实数域三分迭代 次即可达到精度 ;整数域三分要小心平台(相等的连续段),此时改比较相邻点更稳。

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)

三分查找的常见误用

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

3.9 分治范式:分—治—合

分治三步(分-治-合,Divide-Conquer-Combine):

  1. 分(Divide):把规模 的问题拆成 个规模 的子问题;
  2. 治(Conquer):递归求解子问题,直到规模小到可以直接算出(base case);
  3. 合(Combine):把子问题的解合并成原问题的解。

复杂度由递推式给出:

由主定理(Master Theorem),令 :

归并排序(Merge Sort):分成两半,各自排好,再线性合并。

快速排序(Quick Sort):按枢轴(pivot)划分成两段,两段各自排好即可,不需要合并。最好情况每次均分:

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

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)

快速排序为什么不需要「合」

合并的代价是分治复杂度的关键项。归并排序因为「合」要 ,所以递推式里必须带上它;快排的「合」是 (两段已经就位,直接拼接),代价被隐藏在「分」里——这解释了为什么快排的瓶颈是划分质量而不是合并。

3.10 分治经典应用

(1)大整数乘法(Karatsuba)

朴素竖式乘法把两个 位整数相乘需要 。Karatsuba 把每个数拆成高低两半 、,则

朴素的做法需要 4 次子乘法(、、、);Karatsuba 用一次额外加减换掉一次乘法:

于是只需 3 次子乘法:

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

为什么工程中不用手写 Karatsuba

CPython 对超大整数使用 Karatsuba 算法(阈值约 70 位,见 CPython 源码 longobject.c),更大的数还会切换到 Toom-Cook。这里手写是为了理解分治如何把 降到 ,实际项目中请直接用语言内置的大整数。

(2)最近点对(Closest Pair of Points)

暴力枚举所有点对是 。分治做法:按 排序后从中线切成左右两半,递归求出左右两半的最近距离 ;再把中线两侧宽度为 的「条带(strip)」内的点按 排序,只需检查每个点后面的常数个(≤ 7)点。

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)

在数组 中,若 且 ,则称 是一个逆序对(inversion)。逆序对数量既可用于衡量序列的「无序程度」,也是排序算法交换次数的下界。

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

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(即 、),加左右各 0,答案 2。

(4)快速幂(Fast Exponentiation)

计算 时,若 为偶数则 ,若为奇数则 :

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) 是把递归调用画成树,用来估算复杂度:树高 × 每层的工作量。以 为例:

层节点数每节点代价该层总代价
0
1
2
…………

共 层,每层 ,总计 —— 与主定理结论一致。

Python 递归深度

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

3.12 回溯法(Backtracking)

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

通用模板:

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 数组标记已选元素,避免同一元素被重复使用。

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] 这类重复。

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 剪枝,是「可行性剪枝」的典型。

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 皇后——用位运算集合 判断冲突,是最经典的强剪枝示例。

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 是同一套状态与转移方程的两种实现,区别只在遍历顺序和是否显式建表。

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 里,直观需要手动初始化
适用场景状态转移有大量「不可达」分支、拓扑序不明显状态空间规则、需要极致常数与空间

怎么选

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

3.14 三大范式选型对比

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

四、注意事项与常见坑

什么时候不能用这些方法

- 数据无序且查询次数很少:为了二分先排序是 ,不如直接顺序查找 。二分的收益只有在「一次排序、多次查询」时才体现。

- 数据结构不支持随机访问:链表上「二分」没有意义——定位中点本身就要 ,总复杂度退化到 。请改用跳表、平衡树等结构。

- 判定函数不单调:二分答案的前提是「 可行 ⇒ 所有更大的 也可行」(或反向)。若可行性忽真忽假,二分会返回一个无意义的结果且不会报错——这是最难发现的 bug,务必先用小数据暴力验证单调性。

- 函数非单峰:三分查找对多峰函数只能收敛到局部极值。

- 递归深度与 同阶:改用迭代或显式栈。

- 子问题重叠严重:分治会做重复计算,应改成动态规划(例如「斐波那契」用分治递归是 ,用 DP 是 )。

其他高频坑

1. mid 取整方向与更新语句不匹配导致死循环(见 3.5)。

2. 循环退出后直接访问 a[left] 导致越界,忘记判断 left < len(a)。

3. feasible 函数写了 ,使二分答案整体退化;判定函数必须尽量线性。

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])。请以 找出 target 的下标,不存在返回 -1。数组中无重复元素。

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

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

第三步:实现。

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:

轮次leftrightmidnums[mid]哪半有序判定新区间
10637左半 [4..7] 有序4 <= 0 < 7 为假[4, 6]
24651左半 [0,1] 有序0 <= 0 < 1 为真[4, 4]
34440—命中返回 4

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

练习 2(二分答案)

LeetCode 875 爱吃香蕉的珂珂:piles[i] 表示第 堆香蕉的数量,警卫将在 小时后回来。珂珂每小时选择一堆吃掉 根(不足 根就吃完这堆并停止本小时),求能在 小时内吃完的最小 。

提示:判定函数为 sum(ceil(p / k) for p in piles) <= h,它关于 单调不增。答案区间是 。

练习 3(分治)

LeetCode 493 翻转对(或《剑指 Offer》51 数组中的逆序对):统计满足 且 的数对个数,要求 。

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

练习 4(回溯 + 剪枝)

LeetCode 22 括号生成:给出 对括号的所有合法组合。

提示:用 open、close 两个计数器剪枝——open < n 才能放左括号,close < open 才能放右括号。这两条剪枝直接把 的枚举压到卡特兰数 。

练习 5(三分查找)

已知 在 上先增后减, 只能通过一次函数调用求值,求最大值点,误差不超过 。

提示:直接用 3.8 节的 ternary_search_max,迭代约 次;若 可导,改为对导数二分会更快。

六、常见问题 FAQ

为什么 Python 的 bisect 模块只提供了 bisect_left 和 bisect_right,没有「查找等于」?

因为「第一个 」和「第一个 」是更基础的位置语义:bisect_left(a, x) 就是 lower_bound;判断是否命中只需 i = bisect_left(a, x); i < len(a) and a[i] == x。「等于」可以由它们组合得到,反过来则不行。这也解释了为什么工程代码里 lower_bound 比「找等于」更常用。

二分查找用递归写和用迭代写有区别吗?

结果是相同的,复杂度也是相同的 ,但递归版每次调用有函数调用开销且占用栈空间(深度 ,通常无风险)。工程上优先迭代:常数更小、没有 RecursionError 风险、便于编译器优化。

分治和动态规划到底怎么区分?

关键看子问题是否重叠。分治假设子问题相互独立(归并排序里左半和右半互不影响),重复计算不存在;DP 专门处理子问题重叠的情况,用表格或缓存复用结果。判定方法:画出递归树,若不同分支出现相同参数,就应该用 DP。

回溯的时间复杂度怎么估?

数决策树的节点数。全排列是 ( 个叶子,每个叶子拷贝长度为 的解);子集是 ( 个节点);N 皇后在最坏情况下是 ,但位运算剪枝让实际访问的节点数远小于此。面试时给出「决策树大小 × 每个节点的工作量」即可,不必给出紧确界。

相关笔记

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

参考来源