观察题目是否反复出现“数组”对应的数据访问、状态压缩或边界推进特征。
AlgoViz Lab交互式算法学习二分查找：模式识别与解题模板
本专题包含 7 道题。先辨认输入结构和目标，再选择能够持续保持关键不变量的算法，而不是只记住某一道题的代码。
高频模式
观察题目是否反复出现“二分查找”对应的数据访问、状态压缩或边界推进特征。
观察题目是否反复出现“矩阵”对应的数据访问、状态压缩或边界推进特征。
观察题目是否反复出现“分治”对应的数据访问、状态压缩或边界推进特征。
核心模板
- 先写清输入规模、目标值和允许修改的数据。
- 定义每一步开始和结束时必须成立的不变量。
- 把循环、递归、队列或状态转移拆成可验证事件。
- 用最小输入、重复值和退化结构验证边界。
常见错误
- 只根据样例选择算法，没有核对复杂度上限。
- 更新多个指针或状态时破坏旧值依赖。
- 忽略空输入、重复值、断开结构或极端顺序。
- 代码结果正确，但解释没有说明为什么不会漏解或重复。
代表题
搜索插入位置
返回 target 的下标；不存在则返回应插入位置。
搜索二维矩阵
在每行升序且行间有序的矩阵中搜索目标。
寻找峰值
找到任意一个严格大于左右邻居的峰值下标。
搜索旋转排序数组
在无重复旋转升序数组中搜索目标。
在排序数组中查找元素的第一个和最后一个位置
返回目标值的第一个和最后一个下标。
寻找旋转排序数组中的最小值
找出旋转升序数组中的最小值。
寻找两个正序数组的中位数
在 O(log(m+n)) 时间内求两个升序数组中位数。