本博客是GP_二分/01–10 节的总复习以A/B 两套模板为总纲串起标准二分、边界查找、旋转数组、答案二分、切割法。学完整册后用它串一遍面试前刷它收尾。对应代码练习在01_认识二分/…10_两数组中位数/各目录的practice.py。每个知识点总结后面附完整实现纯函数不含测试代码。0. 先立骨架10 题是怎么互相长出来的01 认识二分(每次扔一半, log n) └── 02 边界心法(模板A/B lower/upper_bound 原子操作) ├── 03 标准二分(模板A) ──────────┐ ├── 04 搜索插入位置(模板B) │ ├── 05 左右边界(模板B完全体) │ 模板不变 ├── 06 旋转搜索(A哪半有序) │ 只换比较对象 ├── 07 旋转最小值(B跟hi比) │ ├── 08 平方根(B, 最后一个可行) │ │ └── 09 珂珂(答案二分: 二分速度而非下标) └── 10 两数组中位数(A, 切割线, 压轴)三条贯穿全册的主线主线一句话用在哪两套模板A 找确切值命中即返回B 找边界hi mid 留着答案每题先选模板配对铁律mid ± 1配lo hihi mid配lo hi防死循环/差一位三步心法定区间 → 守不变量 → 查收尾每题的思考顺序★ 总纲两套模板、配对铁律与使用场景这一节是全篇的核心。二分题十次错八次不是找不到而是死循环hi mid配错 while和差一位该返回 lo 还是 lo-1。根因都是没想清楚模板的配对关系。先把两套模板焊死后面 8 道题全是换皮。模板 A · 找确切值左闭右闭命中即返回defsearch(nums,target):lo,hi0,len(nums)-1# ① 闭区间hi 是最后一个下标whilelohi:# ② 区间里还有数lohi 剩一个也要查mid(lohi)//2ifnums[mid]target:returnmid# 找到就走ifnums[mid]target:lomid1# ③ mid 确定不是答案连它扔掉else:himid-1# ③ 同上return-1# 区间空了 不存在三件套一组出现不能混搭hi len-1/while lo hi/mid ± 1。逻辑根基比较完 midmid 自己确定不是答案——所以敢连它一起扔±1。模板 B · 找边界左闭右开hi mid 留着答案deflower_bound(nums,x):lo,hi0,len(nums)# ① 开区间右端答案可能是 len插到末尾whilelohi:# ② 候选答案区还非空mid(lohi)//2ifnums[mid]x:lomid1# ③ mid 确定不行扔else:himid# ★ mid 可能就是答案必须留下returnlo# lo 第一个满足条件的位置逻辑根基mid可能是答案本身——不能扔只能hi mid把它留在区间里退出时 lo 收拢到分界线自带含义直接返回。配对铁律与死循环现场mid ± 1配while lo hihi mid配while lo hi。配错不是差一位就是死循环。死循环怎么来的——拿模板 B 的身体配模板 A 的头lo,hi0,len(nums)-1# 左闭右闭whilelohi:# ✗ 配错mid(lohi)//2ifnums[mid]x:himid# 留着 mid...# 当 lo hi 时 mid lo hi走 hi mid 区间不变 —— 原地转圈永不退出修法就是模板 B 的两处hi len(nums)while lo hi——区间空lo hi就停分界线已收拢。使用场景对照表拿到题先查这张表题目信号模板收尾要点章节有序数组找 target不存在返回 -1A命中 return mid / 空 -103没找到要返回插入位置Blo 就是插入点可为 len04“第一个 / 最后一个 、”Blower/upper_bound 原子操作02、05重复元素找左右边界B × 2左 lb右 ub − 1双检查存在05旋转数组里找 targetA先判哪半有序值域定位06旋转数组找最小值B 变体跟 hi 比不跟 lo 比hi mid 不减一07“最后一个满足条件”如 mid² xB答案 lo − 1第一个不可行减一08“最小的满足 / 最大的不超过”B check二分答案值不是下标09两个有序数组找中位数A二分切割线±inf 哨兵10三个思维转换模板不变只换三样东西“最后一个可行” → “第一个不可行 − 1”模板 B 只会找第一个满足条件的位置把最后一个翻译过去是标准套路05 右边界、08 平方根都用它。二分下标 → 二分答案值08 到 09 的跨越——数组不给了单调性长在答案空间上k 越大耗时越短照样折半。比较对象随便换nums[mid] vs target03→nums[lo] vs nums[mid]06 哪半有序→nums[mid] vs nums[hi]07→check(mid) vs 009→ 切割线两侧10。模板 A/B 从未变过变的只是比较什么——这就是背模板的意义。01 · 认识二分一句话本质在单调的东西上每次比较确定性扔掉一半log n 步定位目标。猜 1..100 里的 37 第1步 猜 50 - 大了 扔掉 51~100剩 1~49 第2步 猜 25 - 小了 扔掉 1~25 剩 26~49 第3步 猜 37 - 中了要点敢扔一半的依据是单调性比 mid 小的全在左边。无序数组扔哪半都是赌命。O(log n) 的量级数据翻倍步数 1——10 亿规模只要 30 步。看到有序→ 想二分用二分 → 先确认单调或能构造单调见 09。公式n 缩到 1 要 log₂n 轮 → 时间 O(log n)。完整实现defguess_binary(n,target):二分猜 1..n 里的 target返回步数。lo,hi1,n steps0whilelohi:mid(lohi)//2steps1ifmidtarget:returnstepsifmidtarget:lomid1else:himid-1returnsteps02 · 边界心法原子操作一句话本质一切边界题 lower_bound第一个 x和upper_bound第一个 x两个原子操作的拼装——两函数只差一个比较符。nums [1, 3, 3, 3, 5, 7]x 3 lb1 ub4 └── 出现区间 [1, 4) → 左边界 1右边界 3个数 4−13“x 的出现区间 [lb, ub)”长度 x 的个数——边界题全部由它变现。要点循环不变量“答案永远在 [lo, hi] 里”——能确定不含才扔mid 可能是答案就留。lower_bound(x)bisect_leftupper_bound(x)bisect_right。04/05/08 直接 import 这两个函数当积木09 的答案二分也是同一骨架比较符换成 check 函数。公式O(log n) / O(1)。完整实现deflower_bound(nums,x):第一个 x 的下标模板 B左闭右开hi mid。lo,hi0,len(nums)whilelohi:mid(lohi)//2ifnums[mid]x:lomid1# mid 和左边全 x答案在右else:himid# nums[mid] xmid 可能就是答案returnlodefupper_bound(nums,x):第一个 x 的下标和 lower_bound 只差 vs 。lo,hi0,len(nums)whilelohi:mid(lohi)//2ifnums[mid]x:lomid1else:himidreturnlo03 · 标准二分LC 704一句话本质模板 A 的标准形态——找到即返回面试唯一要求是一次写对。nums [-1, 0, 3, 5, 9, 12] target 9 lo0 hi5 mid2 nums[2]3 9 扔左lo3 lo3 hi5 mid4 nums[4]9 9 命中返回 4要点三件套一组出现hi len-1/while lo hi/mid ± 1。单元素脑内跑收尾自查[5]找 5 → lohi0mid0 命中。两个常见手误当场现形hi len(nums)越界while lo hi漏查单元素区间。收尾只有两种返回 mid 或 -1。公式每轮区间减半 O(log n)几个变量 O(1)。完整实现defsearch(nums,target):模板 A左闭右闭命中即返回。lo,hi0,len(nums)-1whilelohi:mid(lohi)//2ifnums[mid]target:returnmidifnums[mid]target:lomid1else:himid-1return-104 · 搜索插入位置LC 35一句话本质“没找到返回插入位置” lower_bound(target)——模板 B 一发入魂。nums [1, 3, 5, 6] target5 - 2命中5 就在下标 2 target2 - 1插到 3 前面第一个 2 的位置 target7 - 4比谁都大没有 7 的返回 len要点hi 初始len(nums)不是len-1插入点可以在数组末尾之后——开区间右端要给足。退出时 lo 自带含义[0, lo) 全 target[lo, len) 全 target——lo 就是分界线头尾 case 零特判。三种情况命中/插中间/插两端被模板天然合一。公式O(log n)。完整实现defsearch_insert(nums,target):答案 第一个 target 的下标模板 B。lo,hi0,len(nums)whilelohi:mid(lohi)//2ifnums[mid]target:lomid1else:himidreturnlo05 · 查找左右边界LC 34一句话本质左右边界 lower_bound(t)和upper_bound(t) − 1两个查找函数只差一个比较符对照着写一遍模板 B 就长在手上了。nums [5, 7, 7, 8, 8, 10] target 8 lb3 ub5 └── 出现区间 [3, 5) → 左边界 3右边界 4要点“最后一个满足” → “第一个不满足” − 1模板 B 只会找第一个这个翻译是边界题的标准思维转换。存在性双检查缺一不可left len(nums)target 比所有数大越界取 nums[left] 会崩nums[left] ! targettarget 落在两数之间分界线存在但不等于 target。空数组被left len天然覆盖len0 时 left0len——零特判。公式两次模板 BO(log n)。完整实现defsearch_left(nums,target):第一个 target 的下标。lo,hi0,len(nums)whilelohi:mid(lohi)//2ifnums[mid]target:lomid1else:himidreturnlodefsearch_right(nums,target):第一个 target 的下标只差 。lo,hi0,len(nums)whilelohi:mid(lohi)//2ifnums[mid]target:lomid1else:himidreturnlodefsearch_range(nums,target):leftsearch_left(nums,target)ifleftlen(nums)ornums[left]!target:return[-1,-1]return[left,search_right(nums,target)-1]06 · 旋转数组搜索LC 33高频一句话本质有序被打断成两段升序但每切一刀必有一半有序——先判断哪半有序再用值域决定 target 在不在那半里。[4, 5, 6, 7, 0, 1, 2] lo mid hi nums[lo]4 nums[mid]7 → mid 落在高段左半 [lo..mid] 有序 有序左半的值域 [4, 7)target 在里面吗在就扔右半不在就扔左半要点判断只看一条nums[lo] nums[mid]成立则左半有序否则右半有序。有序的那半用值域[nums[lo], nums[mid])判断 target 在不在——把有序才能二分用回局部。命门等号必须有。区间缩到 1~2 个元素时 lo midnums[lo] nums[mid]这段其实有序写成会误走右半有序分支。本题前提元素互不相同有重复LC 81时该判断失效只能lo 1保守收缩最坏 O(n)——主动提这个区别是加分点。公式模板 A找确切值 每轮 O(1) 的哪半有序判断 → O(log n)。完整实现defsearch_rotated(nums,target):lo,hi0,len(nums)-1whilelohi:mid(lohi)//2ifnums[mid]target:returnmidifnums[lo]nums[mid]:# 左半 [lo, mid] 有序ifnums[lo]targetnums[mid]:himid-1# target 在有序左半的值域里else:lomid1else:# 右半 [mid, hi] 有序ifnums[mid]targetnums[hi]:lomid1# target 在有序右半的值域里else:himid-1return-107 · 旋转数组最小值LC 153一句话本质没有 target 了——比较对象换成nums[hi]最小值藏在断崖底下。值 5 | ● 4 | ● 3 |● 两段升序最小值 崖底第二段的头 2 | ● 1 | ● --------------------- 3 4 5 1 2要点两种情况nums[mid] nums[hi]崖在 mid 右边 → 最小在 (mid, hi]lo mid 1mid 站高段放心扔nums[mid] nums[hi]mid 在崖底右侧含崖底→hi mid不减一mid 可能就是最小值。为什么跟 hi 比不跟 lo 比nums[mid] nums[lo]无法区分完全有序最小在左端和崖在右最小在右半——同一个比较结果对应两种相反的答案。而 hi 永远站在低段这一边。完全有序时nums[mid] nums[hi]恒成立hi 一路收到 lo0返回 nums[0]——零特判。有重复LC 154时nums[mid] nums[hi]无法定方向只能hi - 1最坏 O(n)。公式模板 B 变体hi mid 配 lo hi→ O(log n)。完整实现deffind_min(nums):lo,hi0,len(nums)-1whilelohi:mid(lohi)//2ifnums[mid]nums[hi]:lomid1# 崖在右边mid 站在高段放心扔else:himid# mid 可能就是最小值必须留returnnums[lo]08 · x 的平方根LC 69一句话本质数组不见了——单调性长在答案空间上t 越大 t² 越大二分从下标升维到答案值。x 8t: 0 1 2 3 4 ... t²: 0 1 4 9 16 ... 可行(≤8)? ✓ ✓ ✓ ✗ ✗ └── 答案 最后一个 ✓ 2要点“最后一个可行” “第一个不可行” − 105 同款转换找第一个mid² x返回 lo − 1。hi x 1不是x要覆盖全体可行x0 时答案 0 1 − 1开区间右端必须给 lo 机会停在 1。跨语言防溢出Python 大整数随便乘但 C/Java 里mid*mid溢出 int——改用整除比较mid x // mid。主动说出这句是加分点。公式O(log x)。完整实现defmy_sqrt(x):最后一个可行 第一个不可行 - 1模板 B。lo,hi0,x1whilelohi:mid(lohi)//2ifmid*midx:lomid1# mid 可行分界线在右else:himid# mid 不可行分界线在 mid 或左returnlo-109 · 爱吃香蕉的珂珂LC 875答案二分 · 高频一句话本质识别信号——题目问最小的k 使吃完时间 h且 k 越大时间越短单调→ 二分答案值不是下标。piles [3,6,7,11], h 8 k: 1 2 3 4 5 6 ... 时间: 27 15 10 8 8 6 ✗ ✗ ✗ ✓ ✓ ✓ ↑ 不可行 | 可行 —— 第一个 ✓ 就是答案k4要点check 函数是本题一半的分数每堆ceil(p/k)求和向上取整用整除(p k - 1) // k浮点 ceil 大数失精度。区间[1, max(piles)1]lo 从 1 起k0 不合法hi 给足——kmax 时每小时清空一堆必可行和 04 的 hilen 同理。hi mid不减一mid 可行时它可能就是答案。结构和 04/05 完全同构——比较从数组值换成 check 的返回值。同族题LC 1011 运包裹、LC 410 分割数组最大值。公式每次 check O(n)共 O(log max(piles)) 轮 →O(n log max(piles))。完整实现defhours(piles,k):速度 k 吃完所有堆要几小时sum(ceil(p/k))。returnsum((pk-1)//kforpinpiles)defmin_eating_speed(piles,h):找最小的可行速度模板 B第一个 hours(k) h 的 k。lo,hi1,max(piles)1whilelohi:mid(lohi)//2ifhours(piles,mid)h:himid# mid 可行试试更小的else:lomid1# mid 不行必须更大returnlo10 · 两数组中位数LC 4选做 · 压轴一句话本质中位数 一条合法切割线——两个数组各切一刀左半元素数固定左半最大 右半最小即合法i 定则 j 定在短数组上二分切割位置。a [1, 3] b [2, 4] 切割a 左边取 1 个(i1)b 左边取 1 个(jhalf-i) 左半 {1, 2} 右半 {3, 4} 合法max(左半)2 min(右半)3 ✓ 偶数个中位数 (2 3) / 2 2.5要点i 定了 j 就定了j half − i——只二分一个变量在短数组上二分① 保证 j 不越界② O(log min(m,n))。合法条件a[i-1] b[j]且b[j-1] a[i]不合法看哪边大了定方向。±inf 哨兵i0a 左半为空取 -infim 取 inf——空半边永远合法特判消失。认出它还是模板 Awhile lo hii ± 1 命中即返回只是比较对象换成了切割线两侧。公式O(log(min(m, n)))。完整实现deffind_median_sorted_arrays(a,b):iflen(a)len(b):a,bb,a# 在短数组上二分m,nlen(a),len(b)half(mn1)//2# 左半元素个数奇数时左多一个lo,hi0,m# 切割线 i ∈ [0, m]whilelohi:i(lohi)//2# a 左半取 i 个jhalf-i# b 左半取 j 个i 定则 j 定a_lefta[i-1]ifi0elsefloat(-inf)a_righta[i]ifimelsefloat(inf)b_leftb[j-1]ifj0elsefloat(-inf)b_rightb[j]ifjnelsefloat(inf)ifa_leftb_rightandb_lefta_right:if(mn)%2:returnmax(a_left,b_left)# 奇数左半最大return(max(a_left,b_left)min(a_right,b_right))/2ifa_leftb_right:hii-1# a 切多了else:loi1# a 切少了returnNone# 输入有序到不了这尾声 · 一页纸收束概念一句话模板 A左闭右闭找确切值hilen-1/lohi/mid±1命中即返回模板 B左闭右开找边界hilen/lohi/himid退出 lo 即分界线配对铁律mid±1配lohihimid配lohi——配错即死循环/差一位原子操作lower_bound 第一个 xupper_bound 第一个 x出现区间 [lb, ub)标准转换“最后一个可行” “第一个不可行” − 1哪半有序nums[lo] nums[mid]等号必须有——旋转数组找 target 的钥匙找最小值跟hi比不跟 lo 比hi mid不减一答案二分“最小的满足 / 最大的不超过” → 二分答案值 check 函数切割法i 定则 j 定j half − i短数组上二分±inf 哨兵面试一句话讲复杂度“每轮区间减半最多 log₂n 轮每轮 O(1) 比较所以 O(log n)。”相关阅读同系列GP_链表/博客.md—— 单链表 10 题 · 从反转到归并排序GP_双向链表/博客.md—— 双向链表 · 从两句口诀到 LFU 缓存含踩坑复盘