开始前应具备
- 能解释循环不变量
- 熟悉整数除法和数组边界
- 理解单调递增与单调判定
CHAPTER 04 · 单调决策
二分搜索与答案空间
不只在数组里找数，更要学会在满足单调性的答案空间中做决策。
3 个知识小节6 道分层练习4–5 天 建议周期
00
BEFORE LEARNING
先理解为什么学
二分的核心不是“数组有序”，而是答案空间存在真假分界。稳定掌握一种区间定义后，就能把查找、边界和最优化问题统一起来。
完成本章后
- 固定一种边界写法
- 掌握左右边界搜索
- 识别最大值最小化类答案二分
01
CORE LESSONS
知识讲义
01
LESSON
精确查找与循环不变量
什么时候想到它？
在有序数组中寻找一个确定目标值。
闭区间 [left, right] 表示答案仍可能存在的位置。比较 mid 后，被排除的一半必须明确不含目标，因此更新为 mid ± 1。
推导步骤
- 初始化完整闭区间
- 循环条件使用 left <= right
- 计算中点并比较
- 排除包含 mid 的不可能半区
思维模板 / 伪代码
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
if a[mid] == target: return mid
if a[mid] < target: left = mid + 1
else: right = mid - 102
LESSON
左边界、右边界与旋转数组
什么时候想到它？
目标可能重复，需要第一个或最后一个位置；或数组由若干有序段组成。
找到目标后不能立即返回，而要记录候选并继续向目标边界压缩。旋转数组则先判断哪一半有序，再判断目标是否落在该半区。
推导步骤
- 明确寻找第一个真还是最后一个真
- 满足条件时保存候选位置
- 继续向对应方向收缩
- 循环结束后验证候选是否合法
思维模板 / 伪代码
answer = -1
while left <= right:
mid = ...
if is_valid(mid):
answer = mid
right = mid - 1 # 继续找左边界
else: left = mid + 103
LESSON
在答案空间上二分
什么时候想到它？
要求最小化最大值、最大化最小值，并且给定候选答案后容易判断是否可行。
先确定答案上下界，再设计单调判定函数 feasible(x)。当 x 越大越容易满足或越难满足时，真假分界就是需要寻找的最优答案。
推导步骤
- 写出答案可能的最小和最大值
- 实现候选答案的可行性判断
- 确认真假随 x 的单调方向
- 使用边界二分找到第一个可行值
思维模板 / 伪代码
left, right = min_answer, max_answer
while left < right:
mid = (left + right) // 2
if feasible(mid): right = mid
else: left = mid + 1
return left02
READING
延伸阅读
先读完本站讲义并尝试练习；遇到推导不清的地方，再回到原始教程深入阅读。
03
PRACTICE LADDER
按作用分层练习
题量由知识点决定，不再固定为 5 道。先完成“入门”和“模板”，再做变式与综合；挑战题可以留到复习阶段。
入门认识结构模板独立复现变式迁移条件综合组合技巧挑战延后突破
精确查找与循环不变量
1 道 · 依次完成
LC 704入门简单
二分查找
Binary Search
为什么选：固定闭区间二分模板。
左边界、右边界与旋转数组
4 道 · 依次完成
LC 35模板简单
搜索插入位置
Search Insert Position
为什么选：理解循环结束后的插入边界。
LC 34变式中等
在排序数组中查找元素的第一个和最后一个位置
Find First and Last Position
为什么选：分别寻找左边界和右边界。
LC 153变式中等
寻找旋转排序数组中的最小值
Find Minimum
为什么选：从旋转数组中识别有序关系。
LC 33综合中等
搜索旋转排序数组
Search Rotated Array
为什么选：先判断有序半边，再判断目标所在区间。
在答案空间上二分
1 道 · 依次完成
LC 875挑战中等
爱吃香蕉的珂珂
Koko Eating Bananas
为什么选：把速度作为答案并设计单调可行性判断。
04
PERSONAL NOTEBOOK
我的学习笔记
我如何识别这个模式？今天卡在哪里？下次需要先检查什么？
笔记保存在当前浏览器