算法-查找与分治
这篇笔记讲什么
查找、分治、递归、回溯是四件互相咬合的事:分治是「把大问题切成同型小问题」的范式,递归是它的实现手段,查找(尤其是二分)是分治思想在有序数据上的极致简化,回溯则是递归在枚举问题上的暴力外壳。
读完你应该能:手写四种二分边界变体而不出错、识别「最小化最大值」型二分答案题、写出归并/快排的递推式、用回溯模板解决全排列/子集/组合总和/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):
| 轮次 | left | right | mid | a[mid] | 判定 | 新区间 |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 2 | ,right = mid-1 | [0, 1] |
| 2 | 0 | 1 | 0 | 1 | ,left = mid+1 | [1, 1] |
| 3 | 1 | 1 | 1 | 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 + 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 二分答案:把「最优化」变成「判定」
适用信号:题目问「最小的最大值」「最大的最小值」「最少需要多少」「能否在 步内完成」,且可行性关于答案是单调的——即若 可行,则所有比 更「宽松」的值也可行。
套路四步:
- 确定答案范围
[lo, hi]:从题目约束推出上下界(不要图省事写0到10**18,虽然也能过,但会掩盖越界 bug)。 - 写判定函数
feasible(x):给定候选答案 ,判断是否可行。它通常是一次 的贪心扫描。 - 确定单调方向:是「可行域在右边」(求最小可行值)还是「可行域在左边」(求最大可行值)。
- 套模板:求最小可行值用
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。
| 轮次 | 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) 的核心想法:如果数据是近似均匀分布的,那么可以用数值比例去猜位置,而不是死板地取中点。
斐波那契查找(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):
- 分(Divide):把规模 的问题拆成 个规模 的子问题;
- 治(Conquer):递归求解子问题,直到规模小到可以直接算出(base case);
- 合(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) 是把问题交给「规模更小的同一个函数」来解。一个正确的递归必须有两个要素:
- 基准情形(base case):规模小到可以直接给出答案,否则会无限递归;
- 递归关系(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:
| 轮次 | 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] 无法判断哪边有序),需要改成「先收缩相等边界」,复杂度退化为 最坏。
练习 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-索引 / 学习路线图:回到总导航安排学习顺序
参考来源
- OI Wiki · 二分:二分查找、二分答案与三分查找的中文系统讲解
- OI Wiki · 分治:分治范式与经典分治问题
- OI Wiki · 回溯法:回溯模板与剪枝技巧
- OI Wiki · 快速幂:快速幂与矩阵快速幂
- OI Wiki · 复杂度:主定理与递归式复杂度
- cp-algorithms · Binary Search:二分的边界处理与实现细节
- cp-algorithms · Ternary Search:三分查找的正确性与整数实现
- GeeksforGeeks · Closest Pair of Points:最近点对条带内的常数比较界
- MIT OCW 6.006 Introduction to Algorithms:分治、递归树与主定理的公开课
- LeetCode 33 搜索旋转排序数组 · 34 在排序数组中查找元素的第一个和最后一个位置 · 410 分割数组的最大值 · 875 爱吃香蕉的珂珂 · 51 N 皇后 · 78 子集 · 39 组合总和