Binary Search · 折半收缩

二分查找：左右指针不断折半

二分查找也是一种双指针——只不过两个指针从两端往中间夹。在有序数组里找一个目标 target:lo 和 hi 圈出当前还可能命中的区间，每轮看正中间 mid：猜中就返回； $a[mid]$ 太小说明目标在右半，把 lo 推到 mid+1；太大则把 hi 收到 $mid-1$ 。每轮区间砍半， $O(\log n)$ 步内要么命中、要么区间收空(lo > hi)宣告没有。

默认在 1,3,4,7,9,11,15,20 里找 9。注意变灰的格子：每轮被排除的「半个区间」不会再参与比较——这就是对数级复杂度的来源。换一个不存在的 target（比如 10），可以观察区间一路收缩到 lo > hi。

整型溢出陷阱。教科书常写 mid = (lo + hi) / 2，但当 lo + hi 超过 int 上限时会溢出成负数——2006 年 Google 的 Joshua Bloch 撰文指出，几乎所有教科书的二分实现都带这个 bug。稳妥写法是 $lo + ((hi - lo) >> 1)$ ，永不溢出。JS 的 Number 没有这个上限问题，但在强类型语言里这是必要的写法。

边界为什么是 $mid\pm 1$ 而不是 mid？因为 mid 这一格已经比过了、确定不是答案，必须把它排除在新区间外，否则区间收不动、死循环。配合 while (lo <= hi)（注意是 <=），单元素区间也能正确检查到——这套「闭区间 + $mid\pm 1$ 」是最不容易写错的二分模板。左右对撞的另一道代表题见接雨水。