图解算法通识讲义经典套路
二分查找与单调性收敛区间
核心心智模型：折半砍半，对数降维；只要拥有单调性或可二段性，就能对候选空间对数收敛。
核心交互式算法图解演练沙盒
二分查找模型
有序数组单调折半二分查找演练
步骤 1 / 4
检索目标 Target：33
搜索区间 [low, high]：[0, 8]
计算中点 mid：4 (值: 33)
✓ 命中目标数值
3
[0]L
8
[1]
14
[2]
21
[3]
MID
33
[4]
47
[5]
59
[6]
72
[7]
88
[8]H
防溢出公式：mid = low + (high - low) / 2时间复杂度: O(log N) · 空间复杂度: O(1)
第一轮探测：全区间 [0 ... 8]，中点 mid = (0+8)/2 = 4，nums[4] = 33 == 目标值 33！第一发命中！
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 对数查找 | O(log N) | O(log N) | O(1) | 每次迭代排除一半搜索空间，100万数据仅需 20 次比对。 |
template.java
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;解题核心心法提炼
- 二分的本质不是有序，而是「二段性」：存在某个分界点，左侧全部满足性质，右侧全部不满足。
- 旋转排序数组的核心：mid 的左侧或右侧必然有一侧是完全有序的，在有序那一侧先判定 target 是否在区间内。
- 寻找插入位置或第一个大于等于目标的值，收敛结束后的 left 指针即为目标下标。
常见踩坑警示与避坑指南
- 写成 (left + right) / 2 在大数据量下导致整型溢出为负数。
- 边界更新写成 left = mid 或 right = mid 导致剩余 2 个元素时死循环。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆