搜索插入位置

挨个比，碰到第一个大于等于 target 的位置就是答案。能对，但要 O(n)。数组明明是升序的，这个条件白白浪费了。

在升序数组里，一旦某个位置满足「nums[i] 大于等于 target」，它后面就全满足——这是一条从假到真、只翻一次的分界。二分要找的，就是这条分界的左端点。

准备 · 半开区间 [0, 4)：l 从 0 开始，r 取数组长度 4——注意 r 能等于长度，因为答案可能是「插在最末尾」。现在要找第一个大于等于 2 的位置。

第 1 轮 · 取中点：取区间中点 mid=2，看到 nums[2]=5。拿它跟 target=2 比，决定收哪半边。

第 1 轮 · 判断：5 大于等于 2：5 大于等于 2，说明 mid=2 这个位置满足条件，它有可能就是答案，但它右边的更大，更不可能。所以收右边——关键是 r 收到 mid 本身，不减 1，别把候选丢了。

第 1 轮 · 收缩 r = mid：r 收到 2，范围变成 [0, 2)。下标 2、3 变灰丢掉。mid 虽然是候选，但右边没有更优的，所以连它一起划到区间外。

第 2 轮 · 取中点：新区间 [0, 2)，中点 mid=1，看到 nums[1]=3。

第 2 轮 · 判断：3 大于等于 2：3 也大于等于 2，下标 1 仍然可能是答案。继续往左缩，r 收到 mid=1。

第 2 轮 · 收缩 r = mid：r 收到 1，范围 [0, 1)，现在只剩下标 0 没看过了。

第 3 轮 · 取中点（这次走另一分支）：这轮走另一条分支：mid=0，nums[0]=1 比 target 小。1 排不到 2 前面，下标 0 不可能是插入位置。

第 3 轮 · 收缩 l = mid+1，区间空了：nums[mid] 太小，mid 和它左边全丢，l 跳到 mid 加 1 等于 1。现在 l 和 r 都是 1，区间空了，循环结束。

返回 l：收尾时 l 等于 1，就是答案：2 插在下标 1，数组变成 1、2、3、5、6 仍升序。无论 target 在不在数组里，返回的都是 l。

灵魂帧慢放 · 三轮 l/r/mid 收缩：把三轮连起来看：每轮 mid 大于等于 2 就把 r 拉到 mid 保候选，mid 小于 2 就把 l 推过 mid。区间像夹子一样越夹越窄，最后 l 停在那条真假分界的左端，就是插入位置 1。

只要能把问题改写成「第一个满足某条件的位置」，就是 lower_bound：满足时 r=mid 留候选、不满足时 l=mid+1 弃旧，最后返回 l。

雷区实演 · target 比所有数都大：target=7 比谁都大，每轮 nums[mid] 都小于 7，l 一路被推到 4。如果当初把 r 写成 len 减 1 等于 3，这里就到不了 4，会漏掉「插在最后」。这就是 r 必须取 len 的原因。

三个高频追问：区间风格的配套、重复元素返回哪个、mid 防溢出。

本题是 lower_bound 的原子操作。会了它，LC34 找左右边界就是跑两次；x 的平方根、第一个错误版本都是把 check 换一下。想系统练，去二分专题，或问问 AI 助教小欧「lower_bound 和 upper_bound 差在哪」。

三个极端：空数组返回 0、比最小还小返回 0、比最大还大返回 len。半开区间写法不需要任何特判，全自动覆盖。