二分查找
查找 · 有序数组 · 每一步扔掉一半
猜数字的最优策略
「我想了个 1 到 1000 的数，你每猜一次我告诉你大了还是小了」——最优策略人人都会：猜中间。答案「大了」就扔掉下半、「小了」就扔掉上半，每次候选减半，10 次以内必中。二分查找就是这个策略在有序数组上的算法化：维护候选区间 [lo, hi]，每步和中点 arr[mid] 比较，扔掉不可能的一半——O(log n)，10 亿元素最多 30 次比较。
看得见的「扔掉一半」
下面两次查找：先找 17（命中），再找 4（不存在）。红/蓝/黄箭头是 lo / mid / hi，亮着的柱子 = 当前候选区间，暗下去的都是已被证明不可能的。注意第二次：区间收缩到 [2, 1]（lo > hi）彻底清空——循环退出、返回 -1。右侧代码随每一步同步高亮。
前提：数组有序。找 target = 17：候选区间 [lo, hi] = [0, 9]（高亮部分），每次和中点比、扔掉不可能的一半
1function binarySearch(a: number[], t: number): number {
2 let lo = 0, hi = a.length - 1; // 候选区间 [lo, hi]
3 while (lo <= hi) {
4 const mid = (lo + hi) >> 1; // 探针：取中点
5 if (a[mid] === t) return mid; // 命中
6 if (a[mid] < t) lo = mid + 1; // 目标在右半：扔掉左半
7 else hi = mid - 1; // 目标在左半：扔掉右半
8 }
9 return -1; // 区间清空：不存在
10}
n10
target17
[lo, hi][0, 9]
mid—
1 / 16
不变量与小坑
前提：有序。乱序数组要先排序（O(n log n)），一次查找多、排序摊销就值。
不变量：目标若存在，必在 [lo, hi] 内——每次收缩都保持这句话为真，正确性就有了。
溢出坑：
复杂度：每步区间减半 → ⌈log₂(n+1)⌉ 次比较封顶。
不变量：目标若存在，必在 [lo, hi] 内——每次收缩都保持这句话为真，正确性就有了。
溢出坑：
(lo + hi) / 2 在大数组下可能溢出，稳妥写 lo + ((hi - lo) >> 1)。复杂度：每步区间减半 → ⌈log₂(n+1)⌉ 次比较封顶。
基础版只回答「在不在」。真正让二分成为面试与竞赛常客的是它的变体：重复元素里找左右边界（lower/upper bound）、旋转有序数组里定位、以及跳出数组、在答案空间上二分（「最小可行速度」「最大最小值」）——这些是查找大类接下来几页的故事。