二分与单调答案 · HTML
数学 / 逻辑形态
维护闭区间 [lo,hi]，不变量为“若 target 存在，则仍在区间内”。比较 a[mid] 与 target 后排除不可能的一侧。
识别信号
- 输入整体有序，或存在可定位的有序半段。
- 任务是找某个值的任意位置而非首末边界。
- 一次比较能确定目标只可能在左侧或右侧。
- 线性扫描可做但要求对数时间。
容易误判的相似信号
| Signal | Why it is different |
|---|
| First True 边界 | 若要首个/末个位置，不应命中立即返回；改用 boundary 模板保留候选。 |
| 答案空间二分 | 输入未必有序而可行性单调时，搜索的是答案值，不是数组下标。 |
核心不变量
循环开始时，若 target 存在，它必位于闭区间 [lo,hi]；区间外已被比较证明不可能。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | lo、hi、mid 与 target；闭区间为空的判据是 lo>hi。 |
| Transition | a[mid]<target 则 lo=mid+1；a[mid]>target 则 hi=mid-1；相等立即返回。 |
| Frontier / order | 尚未排除的连续索引区间，而非队列或堆。 |
Python 骨架
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
正确性思路
- 有序性保证 a[mid]<target 时 mid 及其左边都不可能命中，反向同理。
- 每次把 mid 排除，区间严格缩小，最终终止。
- 命中时显然正确；区间为空仍未命中，按不变量目标不存在。
复杂度
| Time | Space | Parameters |
|---|
| O(log n) | O(1) | n 为序列长度；每轮候选规模至少减半。 |
边界条件
- 空数组初始 hi=-1，循环不执行。
- 单元素数组要同时覆盖命中与未命中。
- 重复值时返回任一匹配位置。
- 降序数组必须翻转比较方向。
错误模式
| Pattern | Why it fails / fix |
|---|
| 闭区间却写 lo<hi | 可能漏检最后一个候选；闭区间精确搜索用 lo<=hi。 |
| 更新不排除 mid | 写 lo=mid 或 hi=mid 可在相邻元素时死循环。 |
| 旋转数组照搬比较 | 整体不再有序，需先判断哪一半有序。 |
选择与排除规则
- 找任意精确值：闭区间模板最直接。
- 找首末位置：转 binary-search-boundary。
- 数据频繁更新而查询少：先排序的成本可能不值得。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 返回索引 3。 |
| Setup | 有序序列 [3,8,12,19,25] 中找 19。 |
| Trace | mid=2 值 12，排除左半；新 mid=3 命中。 |
Recall prompts
我的补充