【算法】双指针与滑动窗口（四）：二分——找点与找边界，两类模板与判定设计三课
【算法】双指针与滑动窗口（四）：二分——找点与找边界，两类模板与判定设计三课 摘要 双指针系列第四篇（收官），二分专题。开篇先立两类模板：找点（l<=r + mid±1，== 是终点、mid 出局）与找边界（l
文章信息
- 原文链接：https://jiayq.blog.csdn.net/article/details/164821146
- 发布时间：2026-09-11 09:15:00
- 标签：#Golang, #算法, ##开学季·九月创作之星博客挑战赛, ##相向双指针, ##二分
【算法】双指针与滑动窗口（四）：二分——找点与找边界，两类模板与判定设计三课
摘要
双指针系列第四篇（收官），二分专题。开篇先立两类模板 ：找点（l<=r + mid±1，== 是终点、mid 出局）与找边界（l<r + 保 mid 收缩，== 是路标、mid 可能是答案）——循环条件与收缩方式是一组，拆开单换一个就是死循环或漏格子 。然后三课：LC704/35 （裸题；判决书的新形态——指针的最终位置是所有判决的汇总 ，以及”模板是抵达同一不变量的不同路径”）；LC34 （双二分连发；“幸存者要验明身份”——漏了一个守卫，target 不存在时输出垃圾）；旋转三部曲 LC153/33/81 （判定设计三课：锚点选择、哪半有序 + 值域两端、等值退化）。附一个三犯病历：值域半边 ——排除式思维总漏端点，药方是包含式两端卡。首做 vs 重做的对比数据放在结尾：框架生效的实证 。
前置阅读：双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode
1. 两类模板：先分清再动笔
二分所有题的第一问不是”怎么写”，是”找点还是找边界 “——它决定整个模板：
| 找点（LC704/33/81） | 找边界（LC35/34/153） | |
|---|---|---|
| 问题形态 | target 存在吗 / 在哪 | 第一个/最后一个满足条件的位置 |
| mid 的角色 | 判完 == 就出局 | mid 本身可能是答案 ，不能排除 |
| 循环条件 | l <= r | l < r |
| 收缩方式 | mid±1（mid 出局） | r = mid（保 mid）/ l = mid+1 |
| 收尾 | 循环内 return | 循环外 return nums[l]（l==r 即答案） |
循环条件与收缩方式是一组 ，三条配对铁律：
l<=r配mid±1：每格轮流当 mid，全覆盖l<r配r=mid：mid 向下取整保证mid < r，r=mid严格缩小——不死循环l = mid是毒药：l+1==r时mid==l，l=mid原地转圈——l 方向的收缩只能配mid+1
模板错配的代价不是报错，是逼你写出自己跟不动的逻辑 ——我首做 LC153 时把找点模板（l<=r + mid±1）硬套在找边界题上，为了绕开”mid 可能是答案不能排除”的矛盾，判定条件越缠越复杂（三个变量两两比较），最后缠出一个恒假条件 （else 分支的前提与条件自相矛盾，永不执行）。事后看，那个分支死掉反而是幸运——它要是活的，错误方向早把我带沟里了。
2. 第一课 LC704/LC35：裸题、幸存者身份与殊途同归
LC704 二分查找 是找点模板的裸题，六行代码没什么可说的。值得说的是它的判决书——二分的排除论证长什么样：
1
2
3
4
nums[mid] > target 时，数组有序 ⟹ mid 右侧的所有值 > nums[mid] > target
nums[mid] < target 时，对称
⟹ 每次被排除的那一半，每一个元素都被有序性证明了 ≠ target
LC35 搜索插入位置 是找边界模板的裸题：target 不存在时返回插入位置——“第一个 >= target 的位置”。这题我用了条混合的路子：找点模板吃光区间，退出后 return l——凭什么？判决书的新形态：
1
2
3
4
5
每次 l = mid+1，都携带一份判决："nums[mid] < target"
每次 r = mid-1，都携带一份判决："nums[mid] > target"
⟹ 循环退出时：l 左侧的所有格子已被证明 < target
⟹ l 就是"第一个 >= target 的位置" = 插入点
指针的最终位置不是碰巧停在那的——它是所有判决书的汇总。 return l 能对，靠的是这个不变量，不是运气。
这题还有个值得记的认识：标准找边界模板（l<r + r=mid 保 mid）和我的混合解法殊途同归 ——两条路退出时 l 的语义完全相同。模板不是圣旨，是抵达同一个不变量的不同路径 ——能自己换算模板，才算真的懂了模板。
3. 第二课 LC34：幸存者要验明身份
有序数组中 target 的第一个和最后一个位置。
[5,7,7,8,8,10], 8→[3,4]。
这题 = LC35 × 2：左边界是”第一个 >= target”原样，右边界是它的镜像（“最后一个 <= target”）。首做三版（线性扩张越界 panic → 死循环嵌套死代码 → 双二分终版），重做两版，两段病历都值钱：
首做第一版 ：找到 target 后用 while 向两边线性扩张——[8,8,8,...,8] 直接退化为 O(n)，二分白做；扩张时 nums[start-1] 没有墙，答案贴下标 0 时 nums[-1] panic。边界也要二分找 ——”找到 target 不停”是找点思维的最后残留：找边界的 == 是路标（继续往边界压），不是出口。
重做版 ：核心逻辑一步到位（左边界 == 保 mid、右边界 == 出 mid——上次卡三版的地方一稿全对），但丢了首做终版里的守卫：
1
2
3
4
if nums[l] != target {
return []int{-1, -1}
}
没有它，target 不存在时输出垃圾（[1,0]）。注释里那句”此时 l == r 一定是第一个 target”是错误断言——l==r 的身份是”第一个 >= target 的位置“，是不是 target 还差一格验证。这就是判决书规范的第二条：排除要有判决，幸存者也要验明身份 ——循环退出时指针停在哪、那格是什么语义、是不是答案，三问缺一不可。
顺带一笔：首做版的 len==0/1 特判在重做版里删了——l <= r 的循环天然覆盖。特判是结构缺陷的补丁，结构对了特判蒸发。
4. 第三课：旋转三部曲——判定设计的三次升级
模板不变，变的只是”一次比较能买到多少信息”。三道题是判定设计的完整课程表。
4.1 LC153 寻找旋转数组最小值：锚点选择
旋转数组从 mid 切开，至少一半是有序的 （唯一的断崖只能落在其中一半）。判定哪半有序只需要一次比较——但和谁比？锚点选nums[r]，不选 nums[l]：
1
2
3
nums[mid] > nums[r] ⟹ 断崖横在 mid 和 r 之间 ⟹ 最小值严格在 mid 右边（mid 出局）
nums[mid] < nums[r] ⟹ [mid, r] 无断崖 ⟹ 最小值在 mid 或其左边（mid 保留）
锚点若是 nums[l]：未旋转数组里 nums[l] 本身就是最小值，”mid 比 l 大”既可能表示 mid 在右段、也可能表示整个数组没旋转——一次比较买不到判定，歧义 。锚点选择的判据就一条：比较的结果必须无歧义地指向一个收缩方向 。
终版六行：
1
2
3
4
5
6
7
8
9
10
for l < r {
mid := (l + r) / 2
if nums[mid] >= nums[r] {
l = mid + 1
} else {
r = mid
}
}
return nums[l]
4.2 LC33 搜索旋转数组：哪半有序 + 值域两端
有了 153 的”哪半有序”，加上值域判断就是 33。首做七用例七错起步，重做时三问流程在纸面上 就抓出了老病（详见第 5 节）。终版结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for l <= r {
mid := (l + r) / 2
if nums[mid] == target { return mid }
if nums[l] <= nums[mid] { // 左半有序（<=：l==mid 时天然有序）
if nums[l] <= target && target < nums[mid] { // 值域：两端都卡
r = mid - 1
} else {
l = mid + 1
}
} else { // 右半必有序
if nums[mid] < target && target <= nums[r] { // 两端都卡
l = mid + 1
} else {
r = mid - 1
}
}
}
两个细节各值一行注释：判定用 <= 不是 <——区间缩到两格时 l==mid，nums[l]==nums[mid]（同一个格子），严格 < 会走错分支；值域 nums[l] <= target && target < nums[mid]——mid 端开着 （判过 == 已出局）、l/r 端闭着 （还没判过，必须留在候选里）。
4.3 LC81 旋转数组含重复：等值退化
重复元素让 nums[l] == nums[mid] 可能意味着”断崖藏在等值段里”（[1,1,1,0,1]：左半 [1,1,1] 判”有序”，实际 [l, mid] 里的断崖被等值遮住了）——比较买不到信息 。判决书规范的第三条登场：
1
2
3
4
5
if nums[l] == nums[mid] { // 等值遮住断崖，无法判定哪半有序
l++ // nums[l] == nums[mid] ≠ target（刚判过），扔掉不丢答案
continue // 退化：只排除一个已知非答案的格子
}
最坏情况（全等数组）退化为 O(n)——这是这题的下界 ，退化不是妥协，是数学极限。LC153 首做时我在 > 和 >= 之间犹豫过”等价性”，81 给出了答案：元素互不相同时二者等价，有重复时 == 必须单独处理——等号在约束变化时会分家 。
这题还有一条工程教训：我明知该”拿 33 的底稿加退化分支”，还是从零重写了一套判定——结果 33 版用血换来的两样东西（值域两端、循环条件配对）无声蒸发，五个普通用例反而翻车。改代码用加法不用重写；旧版本的守卫是血换的，要么带上要么说明为什么删。
5. 三犯病历：值域半边
一个病值得单独开节，因为它犯了我三次、每次换一件马甲：
1
2
3
4
5
6
7
第一犯（LC33 首做）：判定写 nums[mid] > target，漏了 target < nums[l] 的情况
→ 主用例 [4,5,6,7,0,1,2] 找 0 当场翻车（0 不在左半值域 [4,7) 里）
第二犯（LC81 首做重写）：换了一套判定体系，值域又只剩 mid 一端
→ [5,6,0,1,2] 找 6 翻车（6 > nums[r]=2，不在右半值域）
第三犯（LC33 重做的思考题）：规则表述"nums[mid] > target 取左边"
→ 纸面上被抓，没进代码
病根诊断：我用排除式思维 （“什么条件下丢这半”）时，排除条件只写了 mid 一端——忘了 target 越过 nums[l]/nums[r] 那一端同样排除这半 。药方是改用包含式 ：每半问一句”target 在不在这半的值域里”——nums[l] <= target < nums[mid]，两端天然都写 ，手就不会漏。
第三犯被纸面抓住是三问流程的胜利：首做时这个病要七个用例实测才暴露，重做时在动笔前的思考题阶段就被摁住了。两分钟的问答，省一整轮提交-翻车-修复。
6. 首做 vs 重做：框架生效的实证
这批题我做了两轮——首做（框架地图建立之前）和重做（三大类框架 + 三问流程之后）：
| 题 | 首做 | 重做 |
|---|---|---|
| LC704 | （首做阶段跳过） | 一版过 |
| LC35 | （首做阶段跳过） | 一版过（混合解法，殊途同归） |
| LC34 | 三版（线性扩张 panic → 死循环嵌套死代码 → 终版） | 两版（核心一步到位，只丢守卫） |
| LC153 | 两版（模板错配出恒假条件） | 一版过 |
| LC33 | 两版（七用例七错起步） | 思考题抓病 + 一版全绿 |
| LC81 | 两版未过（死循环 + 重发明丢细节） | 豁免（判定设计已修完，思维惯性强） |
坑没有白踩，但坑要挂到框架的钩子上才算资产 ——散着放是挫折，挂起来是检查表。值域半边三犯、模板错配、l=mid 死循环、幸存者不验身份，全部在总纲篇的检查表里有自己的行。这就是本系列第一篇（总纲）存在的意义，也是我从”题目做了不少、原理说不出”里爬出来的路。
7. 二分速查表
| 问题 | 判据/口诀 | 出处 |
|---|---|---|
| 找点还是找边界 | mid 判完 == 能不能出局；能→找点模板，不能→找边界模板 | 全类 |
| 循环条件与收缩 | 成组配对：l<=r↔mid±1；l<r↔r=mid；l=mid 是毒药 | 153/34 |
| 值域判断 | 包含式两端卡：nums[l] <= target < nums[mid]——mid 开、l/r 闭 | 33（三犯病历） |
| 判定锚点 | 比较结果必须无歧义指向一个收缩方向（153 锚 nums[r]，33 锚 nums[l] vs nums[mid] 配 <=） | 153/33 |
| 等值买不到信息 | nums[l]==nums[mid] → 退化 l++（判决书：它 ≠ target，扔掉安全）；最坏 O(n) 是下界 | 81 |
| 幸存者身份 | 循环退出时三问：停在哪 / 什么语义 / 是不是答案——差一格验证（nums[l] != target 守卫） | 35/34 |
| 找到 target 停不停 | 找点：== 是出口；找边界：== 是路标，继续压向边界 | 34 |
| 特判 | 结构对了特判蒸发（l<=r 循环覆盖单元素/空数组） | 34/33 |
| 改代码 | 加法不重写；旧版守卫是血换的 | 81 |
| 手推工具 | 判定表先写全四格再翻译；排除式思维易漏端点，改包含式 | 33 重做 |
总结
二分篇收官，整个双指针系列四篇走完。这题群的两个最后收获：
二分是”判定设计”的艺术，不是模板背诵。 两类模板一天就能背会，但每道题真正的工作量在判定：锚点选谁（153）、哪半有序怎么判（33）、等值怎么退化（81）——每次比较要买多少信息，决定了代码的形状 。判定设计的元判据只有一条：比较的结果必须无歧义地指向一个收缩方向，买不到就退化，退化也救不了就换武器（滑窗篇的负数死亡证明是同一句话的滑窗版）。
重做是检验框架的试金石。 六道题首做平均两版多，重做四道一版过、一道两版、一道豁免——提升的不是熟练度，是病在纸面阶段就被抓出来 的能力。三问流程（哪个大类、哪个模板、判决书是什么）把”凭感觉写”换成”对着地图点名”，值域半边这种三犯老病，第三次连代码都没碰到就被摁死在思考题里。
系列四篇至此闭环：总纲立框架，滑窗讲”吃进、判定、吐出”，相向讲”比较、排除、收缩”，二分讲”找点与找边界”。三门算法的账也合上了——回溯在决策树上走路，DP 把树折叠成表，双指针把表折叠成两个指针。下一个系列见。
参考资料
- LeetCode 704. 二分查找
- LeetCode 35. 搜索插入位置
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
- LeetCode 153. 寻找旋转排序数组中的最小值
- LeetCode 33. 搜索旋转排序数组
- LeetCode 81. 搜索旋转排序数组 II
- 双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书
- 双指针与滑动窗口（二）：滑动窗口——吃进、判定、吐出
- 双指针与滑动窗口（三）：相向双指针——比较、排除、收缩
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。