二分查找

最直接：从下标 0 挨个比，碰到 9 就返回。可这样要扫到下标 4，6 个数比 5 次；一百万个数最坏比一百万次。题目都把有序明牌摆你面前了，却还从头扫，等于白白浪费了这个条件。

转折：因为数组有序，正中间那个数就是一道分水岭。用 l、r 圈出范围，mid 取正中间——这是不变量：mid 处的数比 target 小，target 只可能在它右边；比 target 大，只可能在左边。所以每比一次就能整段丢掉一半，不用回头扫。

准备 · 闭区间 [0,5]：左指针 l=0，右指针 r=5，范围就是整个数组。要找的 target = 9。

第 1 轮 · 取 mid：中间下标 mid = (0+5)//2 = 2，nums[2] = 5。拿它和目标 9 比一比。

第 1 轮 · 判断（偏小，丢左半）：5 比 9 小。因为右边全都更大，9 只可能在 mid 右边，mid 这个 5 本身也不是答案——左半连 mid 一起，整段可以扔了。

第 1 轮 · 收缩：把左指针跳到 mid+1 = 3，下标 0、1、2（含那个 5）整段灰掉丢弃。范围缩到 [3, 5]，只剩一半。

第 2 轮 · 取 mid：新范围 [3, 5]，新的中间 mid = (3+5)//2 = 4，nums[4] = 9。再和目标 9 比。

第 2 轮 · 命中！：nums[4] 正好等于 9，命中！返回下标 4。从 6 个数里只比了 2 次就找到——这就是砍半的威力。

再看找不到 · 准备：换个例子：找 6。数组里根本没有 6，看二分怎么干净地收尾、返回 -1。

mid=2 · 偏小收左：mid=2 处是 5，比 6 小，丢左半，l 跳到 3。范围 [3, 5]。

mid=4 · 偏大收右：mid=4 处是 9，比 6 大，这回丢右半，r 收到 mid−1 = 3。现在 l 和 r 都指向 3。

mid=3 · 偏大，区间清空：mid=3 处是 7，比 6 大，r 收到 2。这下 l(3) 越过了 r(2)，范围空了，循环结束——全程没碰到 6，返回 -1。

死循环雷区 · 不能写 l=mid：雷区实演：只剩 [1, 3] 找 3。mid=0 处是 1，偏小，本该把 l 跳到 mid+1。可要是手滑写成 l=mid，l 还是 0，下一轮 mid 算出来又是 0，区间永远不缩——卡死。所以收缩一定要跳过 mid：l=mid+1 或 r=mid−1。

只要数据有序（或答案有单调性），就该想二分：搜索插入位置、x 的平方根、爱吃香蕉的珂珂，全是它的变形。

面试追问：面试追问集中在三处：mid 防溢出、循环条件的等号、二分的真正前提是单调性而非「数组」。

边界三连：三个极端输入：空数组、单元素中、单元素不中。注意它们全靠「闭区间 + l 小于等于 r」自然兜住，不用任何额外特判。

这套 l/mid/r 是一整类题的骨架：LC35 搜索插入位置（找不到返回 l）、LC34 找左右边界，再进阶到「二分答案」LC875 爱吃香蕉的珂珂、LC1011 运送包裹——只要答案有单调性就能二分。更多在 二分查找专题 继续，也可以让小欧帮你讲透「为什么只要单调就能砍半」。