二分查找
本节目标
从搜索区间和循环不变量出发，掌握边界、局部有序与映射后的二分查找。
二分并不是“看到有序数组就套模板”。它的核心是：先明确答案仍可能出现的搜索区间，再借助单调、有序或局部趋势，每轮安全排除一半候选。
识别信号
- 数据整体有序，要求查找一个值或它的插入位置；
- 条件从某个位置开始持续成立，要求第一个或最后一个满足条件的位置；
- 数组经过旋转、矩阵经过映射，但仍能判断一半区域不可能包含答案；
- 相邻元素的升降趋势能说明某一侧必然保留候选。
问题模型
精确查找使用左闭右闭区间 [left, right]：循环开始时，若目标存在，它一定在这个区间中。比较 nums[mid] 后，要么直接返回，要么排除一个已知不含目标的部分。
边界查找改为半开区间 [left, right)。它不问“是否找到”，而问“第一个满足条件的位置在哪里”；即使目标不存在，返回值也仍是合法插入位置。
通用模板
左闭右闭的精确查找：
left = 0, right = n - 1
while left <= right:
mid = left + (right - left) / 2
比较 nums[mid] 与 target
保留仍可能包含 target 的半边
第一个满足条件的位置：
left = 0, right = n
while left < right:
mid = left + (right - left) / 2
if 条件(mid) 成立:
right = mid
else:
left = mid + 1
return left
模板变体
- 查首尾位置：分别取第一个
>= target与第一个> target； - 旋转数组：先识别哪一半有序，再检查目标是否落在该值域；
- 二维矩阵：把一维下标用除法和取模还原为行、列；
- 峰值：根据中点和右邻元素的升降，保留必然存在峰值的一侧。
这些变化改变的是“如何证明可以排除”，而不是机械地背另一套代码。
母题序列
按必学顺序完成：
- 二分查找 必学
- 在排序数组中查找元素的第一个和最后一个位置 必学
- 搜索插入位置 必学
- 搜索旋转排序数组 必学
- 寻找旋转排序数组中的最小值 必学
- 搜索二维矩阵 必学
- 寻找峰值 必学
常见误区
- 区间语义混用：初始化、循环条件和更新规则必须是同一套区间约定。
- 用
target + 1寻找右边界：整数最大值会溢出，应直接使用nums[mid] > target。 - 未验证排除规则：旋转数组和峰值题都不能只因“看起来像二分”就删除一侧。
- 忘记空输入：矩阵映射前先确认矩阵和首行都非空。
迁移方向
下一步可进入二分答案：把搜索对象从数组下标改成速度、容量或最大代价。无论对象是什么，先写出不变量和单调性，再决定二分边界。