02.5.1 二分查找
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.5 二分与排序
这个知识域解决什么问题
二分的本质是在单调候选空间上每次排除一半。本知识域围绕 模板与边界 → 旋转数组与部分有序 → 二分答案 → 二维矩阵与非数组二分 展开;先固定区间不变量与边界口径,再处理分段有序、答案单调与多维候选空间。
知识地图
二分模板与边界(1)
→ 旋转数组与部分有序(2)
→ 二分答案(3)
→ 二维矩阵与非数组二分(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.5.1.1 | 二分模板与边界 | 区间定义、lower/upper_bound、防死循环、mid 防溢出、插入位置、局部峰谷、不变量 | 20 |
| 02.5.1.2 | 旋转数组与部分有序 | 分段有序判定、旋转查找、找最小值、重复元素退化、断点定位、局部有序通用思路 | 20 |
| 02.5.1.3 | 二分答案 | 可行单调、check 判定、最大/最小可行值、吃香蕉、分割数组、运包裹、供暖半径、浮点二分 | 20 |
| 02.5.1.4 | 二维矩阵与非数组二分 | 全有序矩阵映射、行列有序折线、第 K 小、二维峰值、单调函数求根、BST 查找、区间定位 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 写熟区间模板与上下界,2 掌握分段有序的排除策略,3 学会把极值问题转成可行单调的二分答案,最后 4 处理矩阵与非数组候选空间。
自检
- [ ] 能说清左闭右闭与左闭右开两套口径,写出 lower/upper_bound
- [ ] 能解释二分死循环成因并逐轮检查区间收缩
- [ ] 能写旋转数组查找与找最小值,说明重复元素退化
- [ ] 能判断题目是否适用二分答案,写出 check 与方向模板
- [ ] 能区分全有序矩阵与行列有序矩阵的两种搜索策略
- [ ] 能报出各场景时间、空间与口径,并列边界用例