🎯
二分查找
猜数字：每次砍一半，一百万个数最多猜 20 次
💡 打个比方
玩猜数字：我心想 1~100 里的一个数，你猜，我只回答"太大"或"太小"。乱猜可能要 50 次；但如果每次都猜正中间，范围立刻砍一半：100 → 50 → 25 → 12 → 6 → 3 → 1，最多 7 次就锁定。
这就是二分查找：数组必须有序，每次比较中间元素，把一半范围扔掉。100 万个元素？最多 20 次！
二分查找前提：数组已排好序。维护左右边界 l、r，每次看中间 a[mid]：等于 → 找到；太大 → 答案在左半（r = mid - 1）；太小 → 答案在右半（l = mid + 1）。每轮范围减半，复杂度 O(log n)。
🖼️ 大图看明白
📏 二分查找，只要 3 步
- 第 1 步：守住左右边界。l 和 r 框住"答案可能存在的范围"，mid 取中间：mid = l + (r - l) / 2（先减后加防溢出）。
- 第 2 步：比较 a[mid]。等于目标 → 找到了；a[mid] 太大 → 答案在左半，r = mid - 1；a[mid] 太小 → 答案在右半，l = mid + 1。
- 第 3 步：重复到边界交叉。l > r 说明范围空了，没找到。整个过程范围每轮减半，O(log n)。
最常见 bug：① 数组没排序就二分；② 区间开闭不一致（[l, r] 和 [l, r) 混用，l < r 与 l <= r 用错）；③ 死循环——l = mid 和 r = mid 在 l、r 相邻时 mid 不变，永远走不出去。
💻 C++ 怎么写
// 找 target 第一个可能出现的位置（等价 std::lower_bound）
int lowerBound(int a[], int n, int target) {
int l = 0, r = n; // 范围 [l, r)，左闭右开
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < target) l = mid + 1; // 太小，砍左半
else r = mid; // a[mid] 够大，保留左半
}
return l; // 没找到则返回"插入位置"
}
// upperBound = 第一个 > target 的位置；
// 等于 target 的个数 = upperBound - lowerBound
考点提醒：[l, r) + l < r + "r = mid / l = mid+1" 是一套自洽写法：结束时 l == r 就是答案位置；想查"第一个 ≥ x"用 lower_bound 逻辑，"第一个 > x"把判断换成 a[mid] <= target。
✋ 你来试试
题 1：有序数组有 10⁶ 个元素，二分查找最多比较几次？
每轮范围减半：10⁶ → 5×10⁵ → … → 1。2²⁰ = 1048576 > 10⁶，所以最多 20 次。对比一下：从头一个个找（O(n)）最坏要 10⁶ 次——二分快了几万次。
题 2：为什么写 mid = l + (r - l) / 2，而不是 (l + r) / 2？
int 最大约 21 亿。当 l 和 r 都是 15 亿时，l + r 会溢出变负数，mid 就错了；而 (r - l) 最大只有 r，不会超界，再加 l 也安全。小数据时两种写法结果一样，大数据时只有一种不翻车。
🎯 一句话记住：二分查找必须有序；每轮砍半 O(log n)；mid = l + (r-l)/2 防溢出；区间开闭要自洽（[l,r) 配 l<r 配 r=mid）。