🎯 01-数据结构与算法 · 主题 5:二分查找¶
二分是唯一能在有序/可判定结构上达到 $O(\log n)$ 的经典算法,也是手撕题最爱的考点。 本 notebook 目标:吃透三种模板与循环不变量 → 掌握边界二分 → 吃透 7 道高频题 → 通过 25 道自测。
前置:主题 1-4。运行环境:Python 3.8+,无第三方依赖(会对照 bisect 标准库)。
核心概念¶
(a) 🗂️ 二分查找:三种模板、循环不变量与值域二分¶
二分是唯一能在有序/可判定结构上打到 O(log n) 的经典算法,也是手撕题最爱的考点。本 notebook 吃透三种模板与循环不变量,掌握边界二分与值域二分。
flowchart TB
N1["🎯 二分前提与心智模型"] --> N2["循环不变量与复杂度"]
N2 --> N3["标准模板:704 闭区间"]
N2 --> N4["边界模板:lower/upper_bound"]
N3 --> N5["结构变体:33 / 153 / 162"]
N4 --> N6["二分答案:875 爱吃香蕉的珂珂"]
N5 --> N7["进阶:两数组中位数 4"]
N6 --> N8["常见 bug 与边界"]
N7 --> N8
N8 --> N9["模板速查与自测"]
- N1 · 二分前提与心智模型:二分就像猜数字:每次和中间值比一下,直接扔掉一半,所以是 O(log n)。能用二分有两个条件:结构有序(或可判定)、能按中间值排除一半。
- N2 · 循环不变量:循环不变量是"搜索区间到底闭不闭"的约定——想清楚区间语义,代码就不会写出死循环。这是二分最容易翻车的地方,也是面试白板必讲。
- N3 · 标准模板:用闭区间 [l, r],l<=r 循环,mid 命中即返回(LeetCode 704 就是它)。这是最基础的一份模板,其他模板都是它的变形。
- N4 · 边界模板:lower_bound/upper_bound 用左闭右开 [l, r),专门找"第一个满足条件的位置",是 34 题(查找元素首末位置)的基础。
- N5 · 结构变体:旋转数组、寻找峰值、旋转最小值都利用"一半有序"的性质不断缩小区间,属于二分的"结构变体"题。
- N6 · 值域二分(二分答案):现代面试高频——把"猜答案"变成"验证答案",875 爱吃香蕉的珂珂就是标准模板:对速度二分,用"能否吃完"做判定。
- N7 · 进阶:中位数 4:两个有序数组的中位数用二分划分数组,把复杂度压到 O(log min(m,n)),属于硬核加分项,能讲清推导就碾压大部分候选人。
- N8 · 常见 bug 与边界:循环条件写反、mid 计算溢出、死循环(l 不前进)、边界 +1/-1 混乱——每条都要能在白板上指出。
- N9 · 模板速查与自测:结尾三种模板速查表:什么时候用闭区间、左闭右开、值域二分,配合 L1/L2/L3 自测清单收尾。
📷 二分查找:每次与中点比较,区间折半,O(log n) 图源:Wikimedia Commons(开放授权)
猜数字类比:二分到底在干嘛¶
玩过「1~100 猜数字」吗?每次都猜中间数,对方只告诉你大了 / 小了 / 对了,最多 $\lceil \log_2 100 \rceil = 7$ 次必中——这就是二分查找的生活原型:
- 单调性:数轴上的大小关系是单调的,「猜的数 > 答案」和「猜的数 < 答案」把候选区间一分为二;
- 每次排除一半:无论猜大猜小,剩余区间都减半,步数是 $\log_2 N$ 级;
- 判定函数:
mid大了还是小了,本质上就是后面「值域二分」的雏形(答案范围二分)。
记住这个画面:二分 = 不断回答「大了还是小了」,把不可能的一半扔掉。后面所有模板、边界、旋转数组、值域二分,都是这一句话的变体。
§1 二分前提与心智模型¶
什么时候能用二分(两个条件)¶
- 有序:数组有序(或按某种规则排列)
- 可判定单调性:存在一个判定函数 $f(mid)$,答案是「某条件首次/最后成立」的位置——单调序列上可行
💡 现代二分题很多是值域二分(答案在数值范围上二分,如 875、1011),而非直接对数组二分。
循环不变量(背下来)¶
每种模板都要明确:循环过程中,答案一定在区间 $[l, r]$ 内(或 $[l, r)$ 内)。写对不变量,边界就写不错。
复杂度公式¶
每次迭代排除一半:
$$T(n) = T\left(\frac{n}{2}\right) + O(1) \implies T(n) = O(\log n)$$
为什么 mid 要写 l + (r - l) // 2:(l + r) // 2 在 $l + r$ 溢出时出错(C++/Java 面试必问),Python 无溢出但为统一习惯也这样写。
§2 标准模板(闭区间 [l, r],LeetCode 704)¶
循环不变量:若 target 存在,其下标必在 $[l, r]$ 内。
$$\text{while } l \le r: \quad mid = l + \lfloor (r - l)/2 \rfloor$$
- $a[mid] < target$ → target 在右侧 → $l = mid + 1$
- $a[mid] > target$ → target 在左侧 → $r = mid - 1$
- 相等 → 返回 mid;循环结束($l > r$)→ 不存在
为什么循环条件是 $l \le r$:闭区间内只剩一个元素也要判断(mid 可取到 l = r);l < r 会漏掉单元素区间。
⚠️ 死循环根源:
mid永远取不到「不改变区间」的值。闭区间模板两边都 ±1,保证区间严格缩小。
✍️ §2.1 手算二分查找:8 在 [1,3,4,6,8,9,11,15] 里的位置¶
闭区间模板
[l, r]:$m=(l+r)/2$,比较后区间折半——手算 3 步命中,把循环不变量变成具体索引。
设定:nums = [1,3,4,6,8,9,11,15],target = 8,l=0, r=7。
第 1 步:$m=(0+7)/2=3$,nums[3]=6 < 8 → 右半 → l=4(区间 [4,7])
第 2 步:$m=(4+7)/2=5$,nums[5]=9 > 8 → 左半 → r=4(区间 [4,4])
第 3 步:$m=(4+4)/2=4$,nums[4]=8 == 8 → 返回索引 4
| 步 | l | r | m | nums[m] | 动作 |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 6 | l=4 |
| 2 | 4 | 7 | 5 | 9 | r=4 |
| 3 | 4 | 4 | 4 | 8 | ✓ 命中 |
手算收获:
- 每步区间严格折半:长度从 8→4→1,共 $\log_2 8=3$ 步——这就是 $O(\log n)$ 的来源
- 循环不变量:
nums[l..r]始终包含 target(若存在)——第 3 步[4,4]区间只剩一个元素,命中即答案,不命中即不存在 - 下取整
//2防溢出:m = l + (r-l)//2等价且避免 $l+r$ 溢出(C++ 面试常考) - 变体联系:lower_bound(第一个 ≥ target)改 $r=m$;旋转数组/值域二分复用同一循环不变量(本 notebook §5、§8)
下面 numpy 复算。
# ---- §2.1 验证:numpy 复算二分查找 ----
nums = [1, 3, 4, 6, 8, 9, 11, 15]
target = 8
l, r, steps = 0, len(nums) - 1, 0
while l <= r:
m = (l + r) // 2
steps += 1
print(f'第{steps}步: l={l} r={r} m={m} nums[m]={nums[m]}')
if nums[m] == target:
break
elif nums[m] < target:
l = m + 1
else:
r = m - 1
print(f'命中索引 {m}({steps} 步)')
assert steps == 3 and m == 4
print('\n✓ 与手算一致')
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】两个二分基础题:LeetCode 704 二分查找(标准闭区间模板,查确切值)与
# LeetCode 35 搜索插入位置(左闭右开模板,找第一个 ≥ target 的位置)。
# 【算法思路】704:闭区间 [l, r],while l <= r,mid = l + (r-l)//2;
# 命中返回 mid;nums[mid] < target 则答案在右半 → l = mid+1;否则 r = mid-1;
# 区间为空(l > r)仍未找到 → 返回 -1。
# 35:左闭右开 [l, r),while l < r;nums[mid] < target 时 l = mid+1(排除 mid),
# 否则 r = mid(mid 可能就是答案,不能 -1);循环结束 l == r 即插入位置。
# 【变量含义】nums=有序数组;target=查找目标;l / r=区间左右端点;mid=中点下标。
# 【循环不变量】704:答案若存在必在 [l, r] 内,且每轮区间长度严格减半;
# 35:答案(第一个 ≥ target 的位置)恒在 [l, r) 内,且 a[l-1] < target ≤ a[r]。
# 【关键边界】704 用 l <= r(闭区间剩一个元素也要判断,l < r 会漏单元素);
# 35 用 l < r(左闭右开天然处理空区间);mid 用 l + (r-l)//2 防溢出;
# 35 的 r = mid 不能写成 r = mid-1(mid 本身可能就是答案)。
# 【复杂度】两题均为时间 O(log n);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 704. 二分查找:在有序数组中找 target,返回下标,找不到返回 -1
def binary_search(nums, target):
l, r = 0, len(nums) - 1 # 闭区间 [l, r]
while l <= r:
mid = l + (r - l) // 2 # 防溢出取中点(等价于 (l+r)//2)
if nums[mid] == target:
return mid # 命中直接返回
elif nums[mid] < target:
l = mid + 1 # 答案在右半
else:
r = mid - 1 # 答案在左半
return -1 # 区间为空仍未找到
# 35. 搜索插入位置:返回第一个 >= target 的位置(即插入位置),左闭右开模板
def search_insert(nums, target):
# 返回第一个 >= target 的位置(即插入位置),左闭右开模板
l, r = 0, len(nums) # 左闭右开区间 [l, r)
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1 # 排除 mid 及其左侧
else:
r = mid # mid 可能是答案,保留(不 -1)
return l # 循环结束 l == r 即为插入位置
print('binary_search:', binary_search([-1, 0, 3, 5, 9, 12], 9)) # 期望 4
print('binary_search:', binary_search([-1, 0, 3, 5, 9, 12], 2)) # 期望 -1
print('binary_search:', binary_search([5], 5)) # 期望 0
print('search_insert:', search_insert([1, 3, 5, 6], 5)) # 期望 2
print('search_insert:', search_insert([1, 3, 5, 6], 2)) # 期望 1
print('search_insert:', search_insert([1, 3, 5, 6], 7)) # 期望 4
binary_search: 4 binary_search: -1 binary_search: 0 search_insert: 2 search_insert: 1 search_insert: 4
§3 边界模板:lower_bound / upper_bound(左闭右开)¶
问题:找第一个 $\ge target$ 的位置(lower_bound,即 Python bisect_left)与第一个 $> target$ 的位置(upper_bound,bisect_right)。
左闭右开模板 $[l, r)$,循环不变量:
$$\text{答案} \in [l, r), \quad a[l-1] < target \le a[r]$$
$$\text{while } l < r:\quad mid = l + \lfloor (r - l)/2 \rfloor$$
- $a[mid] < target$ → 答案在 $(mid, r)$ → $l = mid + 1$
- $a[mid] \ge target$ → 答案在 $[l, mid]$ → $r = mid$(mid 不减 1,因为 mid 可能就是答案)
关键:r = mid 而不是 r = mid - 1——这就是边界二分的灵魂:mid 本身可能成立,不能排除。
应用:
- 元素出现次数 =
upper_bound(t) - lower_bound(t) - 插入位置(35)=
lower_bound(target) - 第一个和最后一个位置(34)= lower_bound + upper_bound - 1
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】手写两个边界二分模板:lower_bound(第一个 ≥ target 的下标,等价 bisect_left)与
# upper_bound(第一个 > target 的下标,等价 bisect_right),并与标准库对照。
# 用途:元素出现次数 = upper_bound - lower_bound;插入位置(35)= lower_bound。
# 【算法思路】两者都是左闭右开 [l, r) 模板:
# lower_bound:a[mid] < target 时 l = mid+1(排除 mid 及其左侧),否则 r = mid
# (mid 可能就是第一个 ≥ target 的位置,保留);
# upper_bound:a[mid] <= target 时 l = mid+1(等于 target 的也排除),否则 r = mid。
# 【变量含义】a=有序数组;target=查找目标;l / r=左闭右开区间 [l, r);mid=中点下标。
# 【循环不变量】两函数中答案恒在 [l, r) 内;越界时返回 len(a)(即 a 末尾之后,仍是合法插入位置)。
# 【关键边界】lower_bound 用 < 判断、upper_bound 用 <= 判断——这是两者唯一的实质差别;
# r 初始为 len(a)(左闭右开,允许答案 = n);target 大于全部元素时两者都返回 n;
# 空数组返回 0。
# 【复杂度】均为时间 O(log n);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 边界二分模板:lower_bound 找第一个 >= target 的位置,upper_bound 找第一个 > target 的位置(对照 bisect 标准库)
from bisect import bisect_left, bisect_right
def lower_bound(a, target):
# 第一个 >= target 的下标
l, r = 0, len(a)
while l < r:
mid = l + (r - l) // 2
if a[mid] < target:
l = mid + 1
else:
r = mid # mid 可能是答案,保留
return l
def upper_bound(a, target):
# 第一个 > target 的下标
l, r = 0, len(a)
while l < r:
mid = l + (r - l) // 2
if a[mid] <= target:
l = mid + 1
else:
r = mid
return l
a = [1, 2, 2, 2, 3, 5]
print('手写 lower_bound(2) =', lower_bound(a, 2), ',bisect_left =', bisect_left(a, 2)) # 1
print('手写 upper_bound(2) =', upper_bound(a, 2), ',bisect_right =', bisect_right(a, 2)) # 4
print('2 的出现次数 =', upper_bound(a, 2) - lower_bound(a, 2)) # 3
print('lower_bound(4) =', lower_bound(a, 4), '(不存在,返回插入位置)') # 6
手写 lower_bound(2) = 1 ,bisect_left = 1 手写 upper_bound(2) = 4 ,bisect_right = 4 2 的出现次数 = 3 lower_bound(4) = 5 (不存在,返回插入位置)
§4 在排序数组中查找元素的第一个和最后一个位置(LeetCode 34)¶
题目:返回 target 在有序数组中的下标区间 $[first, last]$,不存在返回 $[-1, -1]$。
公式(用边界二分组合):
$$first = \text{lower\_bound}(target), \quad last = \text{upper\_bound}(target) - 1$$
校验:$first \le last$ 且 $a[first] = target$ 才存在;否则返回 $[-1,-1]$。
复杂度:时间 $O(\log n)$,空间 $O(1)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 34 在排序数组中查找元素的第一个和最后一个位置:
# 用 lower_bound / upper_bound 两个边界二分组合,返回 [first, last];不存在返回 [-1,-1]。
# 【算法思路】first = lower_bound(target)(第一个 ≥ target);last = upper_bound(target) - 1
# (第一个 > target 的前一个,即最后一个 = target);
# 校验 first <= last 且 nums[first] == target 才说明 target 真实存在。
# 【变量含义】nums=有序数组(可含重复值);target=查找目标;lo=第一个 ≥ target 的下标;
# hi=最后一个 ≤ target 的下标(= upper_bound-1)。
# 【循环不变量】lo 与 hi 分别由两个边界二分保证为其定义值;空区间 / 不存在时 lo > hi。
# 【关键边界】校验必须同时满足 lo <= hi 与 lo < len(nums)(lo 可能等于 len(nums) 越界,如
# target 大于所有元素时 lower_bound 返回 n)且 nums[lo] == target;
# 空数组:lower_bound 返回 0、upper_bound 返回 0,lo=0 > hi=-1 → 返回 [-1,-1];
# 全数组等于 target([2,2]):lo=0、hi=1 → [0,1]。
# 【复杂度】时间 O(log n)(两次二分);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 34. 在排序数组中查找元素的第一个和最后一个位置:lower_bound + upper_bound 组合
def search_range(nums, target):
lo = lower_bound(nums, target) # 第一个 >= target
hi = upper_bound(nums, target) - 1 # 最后一个 <= target
if lo <= hi and lo < len(nums) and nums[lo] == target:
return [lo, hi] # 存在则返回区间
return [-1, -1] # 不存在
print('test1:', search_range([5, 7, 7, 8, 8, 10], 8)) # 期望 [3, 4]
print('test2:', search_range([5, 7, 7, 8, 8, 10], 6)) # 期望 [-1, -1]
print('test3:', search_range([], 0)) # 期望 [-1, -1]
print('test4:', search_range([2, 2], 2)) # 期望 [0, 1]
test1: [3, 4] test2: [-1, -1] test3: [-1, -1] test4: [0, 1]
§5 搜索旋转排序数组(LeetCode 33)¶
题目:数组在某处旋转(如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]),找 target。
关键观察:二分后,左半段或右半段至少有一段完全有序:
$$a[l] \le a[mid] \implies \text{左半段 } [l, mid] \text{ 有序} \quad \text{否则右半段 } (mid, r] \text{ 有序}$$
决策公式(左半有序时):
$$target \in [a[l], a[mid)) \implies r = mid - 1 \quad \text{否则} \quad l = mid + 1$$
(右半有序对称处理。)
复杂度:时间 $O(\log n)$,空间 $O(1)$。
💡 含重复值的版本(81)把判断改成 $a[l] == a[mid] == a[r]$ 时
l += 1退化为 $O(n)$ 最坏。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 33 搜索旋转排序数组:在「某处旋转过的升序数组」中二分查找 target
# (如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]),要求 O(log n)。
# 【算法思路】关键观察:二分取中点后,左半段 [l, mid] 或右半段 (mid, r] 至少有一段完全有序:
# 若 nums[l] <= nums[mid] 则左半有序——target 落在 [nums[l], nums[mid]) 内就收缩右边界,
# 否则去右半;否则右半有序——对称处理。利用有序段的端点判断 target 归属哪一半。
# 【变量含义】nums=旋转数组;target=查找目标;l / r=闭区间端点;mid=中点下标。
# 【循环不变量】答案(若存在)恒在 [l, r] 内;每轮根据有序段判断精确排除一半,区间严格缩小。
# 【关键边界】有序段判断用 nums[l] <= nums[mid](相等时按左半有序处理,退化场景见 81 题);
# 落在有序段内的判定是 nums[l] <= target < nums[mid](左闭右开,mid 已排除因 nums[mid]≠target);
# 右半对称用 nums[mid] < target <= nums[r];未旋转数组(严格递增)也正确;
# 单元素数组直接命中或返回 -1。
# 【复杂度】时间 O(log n);空间 O(1)。(含重复值的 81 题最坏退化为 O(n),见后。)
# ════════════════════════════════════════════════════════════════════════
# 33. 搜索旋转排序数组:二分后总有一段有序,利用有序段判断 target 所在半段
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # 左半段有序
if nums[l] <= target < nums[mid]: # target 落在有序左半段内
r = mid - 1
else:
l = mid + 1
else: # 右半段有序
if nums[mid] < target <= nums[r]: # target 落在有序右半段内
l = mid + 1
else:
r = mid - 1
return -1
print('test1:', search([4, 5, 6, 7, 0, 1, 2], 0)) # 期望 4
print('test2:', search([4, 5, 6, 7, 0, 1, 2], 3)) # 期望 -1
print('test3:', search([1], 0)) # 期望 -1
print('test4:', search([1, 3], 3)) # 期望 1
test1: 4 test2: -1 test3: -1 test4: 1
§6 旋转数组最小值(153)/ 寻找峰值(162)¶
153:找旋转数组最小值¶
不变量:最小值在 $[l, r]$ 内。
$$a[mid] > a[r] \implies \text{最小值在右半} \ (mid, r] \implies l = mid + 1 \\ a[mid] \le a[r] \implies \text{最小值在左半(含 mid)} \implies r = mid$$
为什么用 $a[r]$ 比较:旋转后右端点附近必有一段最小值侧的下降趋势,$a[r]$ 是「完整有序段」的可靠参照。
162:寻找任一峰值¶
判定:$a[mid] < a[mid+1]$ → 右侧上坡,峰值在右 → $l = mid+1$;否则峰值在左(含 mid)→ $r = mid$。
为什么有效:数组两端视为 $-\infty$,必有峰值;上坡方向一定通向某个峰值。
复杂度:两者均 $O(\log n)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 153 寻找旋转排序数组中的最小值 与 LeetCode 162 寻找峰值——
# 两道「不变量驱动的二分」:153 与右端点比较、162 与相邻元素比较。
# 【算法思路】153:不变量「最小值在 [l, r] 内」。比较 nums[mid] 与 nums[r]:
# nums[mid] > nums[r] ⇒ 旋转点在右侧,最小值在 (mid, r] → l = mid+1;
# 否则最小值在 [l, mid](含 mid)→ r = mid。用右端点比较是因为旋转数组右端附近
# 必有一段下降趋势,nums[r] 是「完整有序段」的可靠参照。
# 162:两端视为 -∞ 必有峰值。nums[mid] < nums[mid+1] ⇒ 右侧上坡 → l = mid+1;
# 否则峰值在左侧(含 mid)→ r = mid。上坡方向必然通向某个峰值。
# 【变量含义】nums=输入数组;l / r=区间端点;mid=中点下标。
# 【循环不变量】153:最小值恒在 [l, r] 内;162:峰值恒在 [l, r] 内(区间收缩方向永远追着「上坡」)。
# 【关键边界】153 循环 while l < r(结束时 l == r 即最小值下标,无需再判);
# 153 的 r = mid 不能 -1(mid 可能恰是最小值);
# 162 的 mid+1 访问需保证 mid+1 < len(while l < r 天然满足);
# 未旋转数组([11,13,15,17])153 直接取最左;162 单元素 / 长度 2 都能正确处理。
# 【复杂度】均为时间 O(log n);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 153. 寻找旋转排序数组中的最小值:与右端点比较,nums[mid] > nums[r] 说明最小值在右半段
def find_min(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] > nums[r]:
l = mid + 1 # 最小值在 mid 右侧
else:
r = mid # 最小值在 [l, mid]
return nums[l]
print('find_min:', find_min([3, 4, 5, 1, 2])) # 期望 1
print('find_min:', find_min([4, 5, 6, 7, 0, 1, 2])) # 期望 0
print('find_min:', find_min([11, 13, 15, 17])) # 期望 11(未旋转)
def find_peak_element(nums):
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < nums[mid + 1]:
l = mid + 1 # 上坡,峰值在右侧
else:
r = mid # 峰值在左侧(含 mid)
return l
print('find_peak:', find_peak_element([1, 2, 3, 1])) # 期望 2
print('find_peak:', find_peak_element([1, 2, 1, 3, 5, 6, 4])) # 期望 5(任一峰值)
print('find_peak:', find_peak_element([1, 2])) # 期望 1
find_min: 1 find_min: 0 find_min: 11 find_peak: 2 find_peak: 5 find_peak: 1
§7 两个正序数组的中位数(LeetCode 4):进阶¶
题目:两个有序数组 $A$(长 $m$)、$B$(长 $n$),求合并后中位数,要求 $O(\log(m+n))$。
中位数公式:
$$\text{median} = \begin{cases} a_{(m+n-1)/2} & m+n \text{ 为奇数} \\ \dfrac{a_{(m+n)/2 - 1} + a_{(m+n)/2}}{2} & m+n \text{ 为偶数} \end{cases}$$
二分划分法思路($O(\log \min(m,n))$):
- 在较短的数组 $A$ 上二分分割点 $i$,另一数组分割点 $j = (m+n+1)//2 - i$
- 满足 $A[i-1] \le B[j]$ 且 $B[j-1] \le A[i]$ 时,左半最大与右半最小即中位数
下面给出易读的归并版($O(m+n)$,理解中位数定义用;面试写二分版)。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 4 寻找两个正序数组的中位数(归并版 O(m+n)):便于理解中位数定义;
# 满足题目 O(log(m+n)) 要求的最优「二分划分版」在下一个代码单元。
# 【算法思路】用归并排序的合并步骤把两个有序数组合并成一个有序数组 merged,
# 然后按中位数定义取:奇数个取正中间 merged[total//2];
# 偶数个取中间两个的平均 (merged[total//2-1] + merged[total//2]) / 2。
# 【变量含义】nums1 / nums2=两个有序数组;merged=合并结果;i / j=两个数组的归并指针;
# total=合并后总长度。
# 【循环不变量】归并过程中 merged 前缀始终有序(每次取两指针所指的较小者);
# 合并结束后剩余段整体拼接,merged 完整有序。
# 【关键边界】归并循环 while i < len(nums1) and j < len(nums2),结束后须拼接剩余段;
# 取中位数下标用 total//2(奇数)与 total//2-1、total//2(偶数);
# 空数组输入:一方为空时 merged 直接等于另一数组(循环不执行、拼接处理);
# 结果类型:奇数返回 float(merged[idx]),偶数返回 (a+b)/2(已是 float)。
# 【复杂度】时间 O(m+n)(合并全程);空间 O(m+n)(merged 数组)。
# ════════════════════════════════════════════════════════════════════════
# 4. 寻找两个正序数组的中位数(归并版 O(m+n)):合并后取中位数,便于理解定义;最优解见下一单元二分版
def find_median_sorted_arrays(nums1, nums2):
# 归并版 O(m+n):便于理解中位数定义;最优为二分划分 O(log(min(m,n)))
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i]); i += 1
else:
merged.append(nums2[j]); j += 1
merged += nums1[i:] + nums2[j:]
total = len(merged)
if total % 2 == 1:
return float(merged[total // 2])
return (merged[total // 2 - 1] + merged[total // 2]) / 2
print('test1:', find_median_sorted_arrays([1, 3], [2])) # 期望 2.0
print('test2:', find_median_sorted_arrays([1, 2], [3, 4])) # 期望 2.5
print('test3:', find_median_sorted_arrays([], [1])) # 期望 1.0
print('test4:', find_median_sorted_arrays([0, 0], [0, 0])) # 期望 0.0
test1: 2.0 test2: 2.5 test3: 1.0 test4: 0.0
手撕二分划分版(硬核推导,$O(\log \min(m, n))$)¶
目标:在两个数组各自的分割点切开,使左半所有数 ≤ 右半所有数,且左右数量平衡。
设 $A$ 是较短数组(长 $m$,保证 $m \le n$,否则交换),在 $A$ 上二分分割点 $i$($A$ 左边取 $A[0..i-1]$,共 $i$ 个,$i$ 范围 $[0, m]$)。由左右数量平衡,$B$ 左边取:
$$j = \frac{m + n + 1}{2} - i \quad (\text{整数除法})$$
合法分割的充要条件(两个交叉大小关系):
$$A[i-1] \le B[j] \;\;\text{且}\;\; B[j-1] \le A[i]$$
不满足时如何移动 $i$(关键推导):
- 若 $A[i-1] > B[j]$:$A$ 左边取多了 → 左移:$r = i - 1$;
- 若 $B[j-1] > A[i]$:$A$ 左边取少了 → 右移:$l = i + 1$。
边界处理(面试必被问,用 $\pm\infty$ 统一):
- $i = 0$:$A$ 左半为空,$A[i-1]$ 视作 $-\infty$(不参与
left_max); - $i = m$:$A$ 右半为空,$A[i]$ 视作 $+\infty$(不参与
right_min); - $j = 0$:$B[j-1]$ 视作 $-\infty$;$j = n$:$B[j]$ 视作 $+\infty$。
取中位数:left_max = max(A[i-1] 或 -inf, B[j-1] 或 -inf),right_min = min(A[i] 或 +inf, B[j] 或 +inf)。
- 总数奇数 → 返回
left_max(左边恰好多一个); - 总数偶数 → 返回
(left_max + right_min) / 2。
复杂度:只对较短的 $A$ 二分 → $O(\log \min(m, n))$,优于归并版 $O(m+n)$,满足题目 $O(\log(m+n))$ 要求。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 4 寻找两个正序数组的中位数(二分划分版 O(log(min(m,n)))):
# 满足题目 O(log(m+n)) 要求的最优解,面试要求手撕。
# 【算法思路】在较短数组 A 上二分分割点 i(A 左半取 A[0..i-1] 共 i 个,i ∈ [0, m]),
# 由左右数量平衡得 B 的分割点 j = (m+n+1)//2 - i;
# 合法分割的充要条件:A[i-1] <= B[j] 且 B[j-1] <= A[i](左右交叉大小关系);
# 若 A[i-1] > B[j]:A 左边取多了 → hi = i-1;若 B[j-1] > A[i]:A 左边取少了 → lo = i+1;
# 边界用 ±INF 统一(i=0 / i=m / j=0 / j=n 时一侧为空);
# 中位数:奇数 → left_max;偶数 → (left_max + right_min) / 2。
# 【变量含义】A / B=两个数组(A 为较短者,长度 m ≤ n);i / j=两数组分割点;half=(m+n+1)//2;
# a_left / a_right / b_left / b_right=四个分割边界值(越界用 ∓INF 兜底);
# INF=float('inf');lo / hi=i 的二分区间 [0, m]。
# 【循环不变量】每轮 i 满足 0 ≤ j ≤ n(由 half 与 i 的范围自动保证);
# 最终找到的 i 使左半最大值 ≤ 右半最小值,即合法全局分割。
# 【关键边界】先保证 len(A) <= len(B)(否则交换,确保 j 不越界);
# 越界取值:i>0 才有 A[i-1],否则 -INF;i<m 才有 A[i],否则 +INF;j 同理;
# 相等元素([1,1,1] vs [1])时交叉条件用 <= 仍成立;
# 空数组(m=0)时 i 恒为 0,a_left=-INF、a_right=+INF,条件退化为平凡成立。
# 【复杂度】时间 O(log min(m, n))(只对短数组二分);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 4. 中位数(二分版 O(log(min(m,n)))):在较短的数组上二分分割点 i,用中位数定义判断分割是否合法
def find_median_sorted_arrays_binary(nums1, nums2):
# O(log(min(m,n))):在较短的数组上二分分割点 i
A, B = nums1, nums2
if len(A) > len(B): # 保证 A 是较短数组(m <= n)
A, B = B, A
m, n = len(A), len(B)
lo, hi = 0, m # 分割点 i 范围 [0, m]
half = (m + n + 1) // 2
INF = float('inf')
while lo <= hi:
i = (lo + hi) // 2
j = half - i
a_left = A[i - 1] if i > 0 else -INF
a_right = A[i] if i < m else INF
b_left = B[j - 1] if j > 0 else -INF
b_right = B[j] if j < n else INF
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2 == 1: # 奇数:中位数 = 左半最大
return float(max(a_left, b_left))
return (max(a_left, b_left) + min(a_right, b_right)) / 2
elif a_left > b_right: # A 左边取多了 → 左移
hi = i - 1
else: # A 左边取少了 → 右移
lo = i + 1
return -1.0 # 理论不可达
print('test1:', find_median_sorted_arrays_binary([1, 3], [2])) # 期望 2.0
print('test2:', find_median_sorted_arrays_binary([1, 2], [3, 4])) # 期望 2.5
print('test3:', find_median_sorted_arrays_binary([], [1])) # 期望 1.0(A 空)
print('test4:', find_median_sorted_arrays_binary([2], [])) # 期望 2.0(B 空)
print('test5:', find_median_sorted_arrays_binary([], [2, 3])) # 期望 2.5(A 空、偶数)
print('test6:', find_median_sorted_arrays_binary([1, 1, 1], [1])) # 期望 1.0(全相等)
print('test7:', find_median_sorted_arrays_binary([1], [2, 3, 4])) # 期望 2.5
print('test8:', find_median_sorted_arrays_binary([0, 0], [0, 0])) # 期望 0.0
print('test9:', find_median_sorted_arrays_binary([1, 3, 5], [2, 4])) # 期望 3.0
test1: 2.0 test2: 2.5 test3: 1.0 test4: 2.0 test5: 2.5 test6: 1.0 test7: 2.5 test8: 0.0 test9: 3.0
§8 值域二分(现代面试高频):875 爱吃香蕉的珂珂¶
题目:每小时吃 $k$ 根,$h$ 小时内吃完所有堆,求最小 $k$。
思路:答案 $k \in [1, \max(piles)]$ 单调——$k$ 越大用时越少。对 k 的值域二分:
$$\text{耗时}(k) = \sum_i \left\lceil \frac{piles_i}{k} \right\rceil$$
判定 $\text{耗时}(k) \le h$ 是否成立,找「首次成立」的最小 $k$。
复杂度:$O(n \log \max(piles))$。
💡 同类:1011 在 D 天内送达包裹的能力、410 分割数组的最大值——**「可行性判定 + 值域二分」**是统一的框架。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 875 爱吃香蕉的珂珂(二分答案/值域二分):求能在 h 小时内吃完所有香蕉堆的
# 最小速度 k。同类框架:1011 在 D 天内送达、410 分割数组最大值。
# 【算法思路】答案 k ∈ [1, max(piles)] 且「越大越快」单调:可行性判定 feasible(k) = 总耗时 ≤ h,
# 其中总耗时 = Σ ceil(piles_i / k)(每堆至少 1 小时,向上取整);
# 对 k 的值域做左闭右开二分:feasible(mid) 成立 → r = mid(尝试更小速度);
# 不成立 → l = mid+1(必须更快);循环结束 l 即最小可行速度。
# 【变量含义】piles=各堆香蕉数;h=允许的总小时数;feasible(k)=判定速度 k 是否可行;
# l / r=速度值域 [1, max(piles)] 的二分区间;mid=候选速度;p=每堆香蕉数。
# 【循环不变量】l 恒为「当前已知最小可行速度」的下界,r 恒为可行上界;
# 二分过程中 [l, r] 内始终存在可行答案(不变量驱动)。
# 【关键边界】下界取 1(速度为 0 无意义);上界取 max(piles)(该速度下每堆 1 小时,必可行);
# ceil 用 math.ceil(p / k),注意整数除法要转 float 或手动 (p + k - 1) // k;
# h >= len(piles) 是可行性前提(每堆至少 1 小时),题目保证。
# 【复杂度】时间 O(n log max(piles))(每轮判定 O(n),二分 O(log max));空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 875. 爱吃香蕉的珂珂(二分答案):对速度 k 做值域二分,用「能否在 h 小时内吃完」作为可行性判定
import math
def min_eating_speed(piles, h):
def feasible(k):
return sum(math.ceil(p / k) for p in piles) <= h
l, r = 1, max(piles) # 值域 [1, max]
while l < r:
mid = l + (r - l) // 2
if feasible(mid):
r = mid # 可行:尝试更小
else:
l = mid + 1 # 不可行:需要更大
return l
print('test1:', min_eating_speed([3, 6, 7, 11], 8)) # 期望 4
print('test2:', min_eating_speed([30, 11, 23, 4, 20], 5)) # 期望 30
print('test3:', min_eating_speed([30, 11, 23, 4, 20], 6)) # 期望 23
test1: 4 test2: 30 test3: 23
§高频补充:搜索二维矩阵(74)/ 搜索旋转排序数组 II(81)/ x 的平方根(69)¶
74:矩阵整体有序 → 一维化二分:mid -> r = mid // n, c = mid % n,把 $m \times n$ 矩阵当作长度 $m\cdot n$ 的有序数组。
81:旋转数组含重复 → 当 nums[l] == nums[mid] == nums[r] 时无法判断哪边有序,只能 l += 1; r -= 1 缩小去重;其余判定与 33 完全一致。
69:值域二分经典——整数二分求最大 ans 使 ans*ans <= x;另附浮点二分($\varepsilon = 10^{-7}$)逼近平方根。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 74 搜索二维矩阵:矩阵每行递增且行首大于上一行末尾(整体有序),
# 用「一维化二分」在 O(log(m·n)) 内查找 target。
# 【算法思路】把 m×n 的矩阵当作长度为 m*n 的连续有序数组:
# 对一维下标 mid 二分,用 r = mid // n、c = mid % n 换算回二维坐标取元素;
# 命中返回 True;值小于 target 去右半(lo = mid+1),否则去左半(hi = mid-1)。
# 【变量含义】matrix=有序二维矩阵;target=查找目标;m / n=行数 / 列数;
# lo / hi=一维化下标区间 [0, m*n-1];mid=一维中点;r / c=换算出的行 / 列。
# 【循环不变量】target 若存在,其一维化下标恒在 [lo, hi] 内(矩阵整体有序保证下标单调)。
# 【关键边界】必须先判空:not matrix 或 not matrix[0] 直接返回 False(防 matrix[0] 越界);
# 坐标换算是关键一步:r = mid // n、c = mid % n(除的是列数 n 不是行数);
# 单行 / 单列 / 空矩阵用例都要覆盖(本单元 6 个测试覆盖全部分支)。
# 【复杂度】时间 O(log(m·n));空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 74. 搜索二维矩阵:一维化二分,把 m*n 的有序矩阵看作长度为 m*n 的有序数组,下标换算回行列
def search_matrix(matrix, target):
# 一维化二分:把 m*n 有序矩阵看作长度为 m*n 的有序数组
if not matrix or not matrix[0]:
return False
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
r, c = mid // n, mid % n # 一维下标 → 二维坐标(关键一步)
v = matrix[r][c]
if v == target:
return True
elif v < target:
lo = mid + 1
else:
hi = mid - 1
return False
print('test1:', search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3)) # 期望 True
print('test2:', search_matrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13)) # 期望 False
print('test3:', search_matrix([[1]], 1)) # 期望 True
print('test4:', search_matrix([[1]], 0)) # 期望 False
print('test5:', search_matrix([], 1)) # 期望 False(空矩阵)
print('test6:', search_matrix([[1, 3]], 3)) # 期望 True(单行)
test1: True test2: False test3: True test4: False test5: False test6: True
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 81 搜索旋转排序数组 II(含重复元素):与 33 题同框架,但需处理
# 「nums[l] == nums[mid] == nums[r]」导致无法判断哪半段有序的退化情况。
# 【算法思路】基本判定同 33:nums[l] <= nums[mid] 时左半有序、否则右半有序;
# 但三者相等时两个半段都可能乱序,无法判定——只能 l += 1、r -= 1 各收缩一位去重;
# 最坏(数组几乎全相等)时每次只缩一位,退化到 O(n)。
# 【变量含义】nums=含重复元素的旋转数组;target=查找目标;l / r=闭区间端点;mid=中点下标。
# 【循环不变量】target 若存在恒在 [l, r] 内;区间收缩时只排除「不可能含 target」的半段或端点重复值。
# 【关键边界】三值相等分支必须最先判断(先于 nums[l] <= nums[mid] 的有序段判定);
# 三值相等时 l += 1、r -= 1 同时缩(只缩一边可能漏元素);
# 其余分支与 33 完全一致(target 落在有序段内用左闭右开比较);
# 经典用例 [1,0,1,1,1] 找 0:三值相等反复收缩后仍能找到——验证退化分支正确。
# 【复杂度】平均 O(log n);最坏 O(n)(全相等数组每次只缩一位);空间 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 81. 搜索旋转排序数组 II(含重复元素):三个值相等无法判断哪边有序 → 左右各收缩一位去重
def search_rotated_ii(nums, target):
# 旋转排序数组 + 重复元素:三值相等无法判定哪边有序 → l+=1, r-=1 去重
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return True
if nums[l] == nums[mid] == nums[r]: # 无法判断 → 两边各缩一步
l += 1
r -= 1
elif nums[l] <= nums[mid]: # 左半有序(判定同 33)
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # 右半有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return False
print('test1:', search_rotated_ii([2, 5, 6, 0, 0, 1, 2], 0)) # 期望 True
print('test2:', search_rotated_ii([2, 5, 6, 0, 0, 1, 2], 3)) # 期望 False
print('test3:', search_rotated_ii([1, 0, 1, 1, 1], 0)) # 期望 True(三值相等经典用例)
print('test4:', search_rotated_ii([1, 1, 1, 1, 1], 1)) # 期望 True
print('test5:', search_rotated_ii([1, 1, 1, 1, 1], 2)) # 期望 False
print('test6:', search_rotated_ii([1], 1)) # 期望 True
print('test7:', search_rotated_ii([3, 1], 1)) # 期望 True
print('test8:', search_rotated_ii([], 1)) # 期望 False
test1: True test2: False test3: True test4: True test5: False test6: True test7: True test8: False
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 69 x 的平方根(整数版)+ 浮点二分版:
# 整数版求最大 ans 使 ans² <= x(向下取整);浮点版以 eps 精度逼近 sqrt(x)。
# 【算法思路】整数版(值域二分):ans 的值域 [0, x] 上二分;mid² <= x 成立则记录 ans = mid
# 并向右找更大的可行解(lo = mid+1),否则 hi = mid-1;循环结束 ans 即平方根整数部分。
# 浮点版:区间 [lo, hi] 二分(先处理 0 < x < 1 时 sqrt(x) > x 的边界,上界取 1);
# mid² < x 时 lo = mid,否则 hi = mid;循环直到 hi - lo <= eps,返回中点。
# 【变量含义】x=被开方数;lo / hi=区间端点;mid=中点;ans=记录的最大可行整数解;
# eps=浮点精度(默认 1e-7)。
# 【循环不变量】整数版:ans 恒为「已扫描过的满足 ans² <= x」的最大值;浮点版:sqrt(x) 恒在 [lo, hi] 内。
# 【关键边界】整数版二分上界取 x(x >= 1 时 sqrt(x) <= x);ans 从 0 开始,x=0 / x=1 直接正确;
# 浮点版 x < 0 返回 None;0 < x < 1 时必须把 hi 提到 1(否则收敛到 0 附近错误值);
# 浮点循环条件是 hi - lo > eps 而非 l < r(浮点永不精确相等);
# mid² 用 mid * mid 即可(Python 大整数无溢出)。
# 【复杂度】整数版时间 O(log x);浮点版 O(log(范围/eps)) 次迭代;两者空间均为 O(1)。
# ════════════════════════════════════════════════════════════════════════
# 69. x 的平方根:整数二分(值域二分),求最大的 ans 使得 ans*ans <= x,只保留整数部分
def my_sqrt(x):
# 整数二分(值域二分):求最大的 ans 使 ans*ans <= x
lo, hi = 0, x
ans = 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
ans = mid # mid 可行,记录并向右找更大的可行解
lo = mid + 1
else:
hi = mid - 1
return ans
def sqrt_float(x, eps=1e-7):
# 浮点二分:在 [lo, hi] 上逼近 sqrt(x),区间宽度 < eps 为止
if x < 0:
return None
lo, hi = 0.0, float(x)
if x < 1.0: # 0 < x < 1 时 sqrt(x) > x,上界取 1
hi = 1.0
while hi - lo > eps:
mid = (lo + hi) / 2
if mid * mid < x:
lo = mid
else:
hi = mid
return (lo + hi) / 2
print('sqrt(4) =', my_sqrt(4)) # 期望 2
print('sqrt(8) =', my_sqrt(8)) # 期望 2(向下取整)
print('sqrt(1) =', my_sqrt(1)) # 期望 1
print('sqrt(0) =', my_sqrt(0)) # 期望 0
print('sqrt_float(2) =', round(sqrt_float(2), 7)) # 期望 1.4142136
print('sqrt_float(0.25)=', round(sqrt_float(0.25), 7)) # 期望 0.5
print('check 2 :', abs(sqrt_float(2) - 2**0.5) < 1e-7) # 期望 True
print('check 0.25 :', abs(sqrt_float(0.25) - 0.25**0.5) < 1e-7) # 期望 True
sqrt(4) = 2 sqrt(8) = 2 sqrt(1) = 1 sqrt(0) = 0 sqrt_float(2) = 1.4142136 sqrt_float(0.25)= 0.5 check 2 : True check 0.25 : True
§9 常见 bug 与边界(面试踩坑区)¶
- 死循环:闭区间模板忘写
l = mid + 1 / r = mid - 1(mid 被反复选中);左闭右开模板r = mid时必须l < mid前提成立 - mid 计算:
(l + r) // 2在 C++/Java 会溢出($l + r$ 超 int 范围),用l + (r - l) // 2 - 循环条件写错:
while l <= r(闭区间)vswhile l < r(左闭右开)——和「mid 是否 -1」配套 - 越界访问:
nums[mid + 1]要确认 mid + 1 < len;nums[l]在空数组直接崩 l + 1 < r开区间模板:mid 要向上取整(l + r + 1) // 2,否则死循环(经典坑)- 二分前提:乱序数组不能二分;旋转数组要先判断哪半段有序
- 浮点二分:用
while r - l > 1e-6而不是l < r(浮点永不精确相等)
§10 面试追问与扩展(加分项)¶
10.1 三种模板速查(写对不变量就写对代码)¶
| 模板 | 区间 | 循环 | mid 归属 | 适用 |
|---|---|---|---|---|
| 标准查找 | $[l, r]$ | $l \le r$ | mid ± 1 | 查确切值 704 |
| 左边界 | $[l, r)$ | $l < r$ | r = mid |
lower_bound / 35 |
| 开区间 | $(l, r)$ | $l + 1 < r$ | mid 归属 | 需要相邻比较时 |
10.2 二分答案(值域二分)判断标准¶
- 答案单调(越大/越小越满足某条件)
- 「最大化最小值」「最小化最大值」类题 100% 是二分答案
10.3 与 bisect 的关系¶
Python 面试可以先用 bisect_left/right 顶复杂度,但要能手写;sortedcontainers 之类不允许。
§11 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 二分查找(LeetCode 704)
- 2. 搜索插入位置(35)
- 3. x 的平方根(69)
- 4. 猜数字大小(374)
- 5. 第一个错误的版本(278)
- 6. 山脉数组的峰顶索引(852)
- 7. 有效的完全平方数(367)
- 8. 寻找比目标字母大的最小字母(744)
- 9. 排列硬币(441)
- 10. 有序数组的平方(977,双指针/二分)
L2 进阶(10 题)¶
- 11. 在排序数组中查找元素的第一个和最后一个位置(34)
- 12. 搜索旋转排序数组(33)
- 13. 搜索旋转排序数组 II(81,含重复)
- 14. 寻找旋转排序数组中的最小值(153)
- 15. 寻找旋转排序数组中的最小值 II(154)
- 16. 寻找峰值(162)
- 17. 寻找两个正序数组的中位数(4)
- 18. 爱吃香蕉的珂珂(875)
- 19. 在 D 天内送达包裹的能力(1011)
- 20. Pow(x, n)(50,快速幂二分)
L3 挑战(5 题)¶
- 21. 乘法表中第 k 小的数(668)
- 22. 找出第 k 小的距离对(719)
- 23. 分割数组的最大值(410)
- 24. 最小化去加油站的最大距离(774,浮点二分)
- 25. 每个小孩最多能分到多少糖果(2226,二分答案)
自测要点¶
- 3 分钟内盲写:704 标准二分 + lower_bound
- 讲清循环不变量(答案始终在区间内)与死循环成因
- 能手推旋转数组 33 的「哪半段有序」判断