搜索插入位置：二分找到「第一个大于等于 target」
有序数组里「找到」和「插入」是同一个分界点。循环结束时不要返回 mid，left 才停在答案上。
插入位置 = 第一个满足 nums[i] ≥ target 的下标。闭区间 [left, right] 上二分：nums[mid] < target 则 left = mid+1（mid 及左边都太小），否则 right = mid−1。不变量：left 左边都 < target，right 右边都 ≥ target。循环结束时 left == right+1，left 就是答案。O(log n)。
这是 LeetCode 35. Search Insert Position。大白话：给你一个升序、元素互不相同的整数数组 nums，再给一个目标值 target。如果 target 在数组里，返回它的下标；如果不在，返回它按顺序插入后应该待的下标。下标从 0 开始，也可以插到最左或最右，最右的下标等于数组长度。
主例数组始终是 [1, 3, 5, 6]。target = 5，5 就在下标 2，返回 2；target = 2，2 不在，应插在 1 和 3 之间，返回 1；target = 7，比所有数都大，应插在末尾，返回 4。再补一个最左：target = 0 应返回 0。
从左到右扫也能做对，但数组有序这件事完全没被用上。有人会说「那就二分，找到就返回 mid，找不到再想办法」——后半句含糊。找不到的时候 mid 已经跳来跳去，你并不能从最后一次 mid 读出插入位置。缺的是一句循环期间不能破的话：答案始终落在 [left, right+1] 里，区间空了就返回 left。
插入位置 = 第一个 ≥ target 的位置
这道题看起来像两问：找到就返回下标，找不到就返回插入位置。有序数组里这两问是同一件事。你要找的不是「等于 target 的那个格子」，而是「第一个大于等于 target 的位置」。数在数组里，这个位置就是它自己；数不在，这个位置就是它该插入的地方，插进去之后左边都比它小，右边都比它大。
升序意味着存在一个分界点：分界点左边的数都小于 target，分界点以及右边的数都大于等于 target。这个分界点的下标，就是题目要的答案。target 比所有数都小，分界点在下标 0；比所有数都大，分界点在下标 n，也就是数组末尾的「虚空一格」。
不要把插入位置理解成「第一个大于 target 的位置」。target = 5 时，第一个大于 5 的是 6，下标 3，答案错了。数在数组里时，插入位置就是它自己，等号必须留下。题目接受「插到它自己所在的下标」，因为元素互不相同，插在它前面和返回它的下标是同一个数。
重述二分题先写清「找的是什么位置」。本题找的是 lower_bound：第一个 ≥ target 的下标。查找和插入共用这一个出口。
二分收缩：小于 target 的全排除
一开始 left = 0，right = n−1，整段数组都还在考虑。只要 left <= right，区间里至少还有一个数，取出中点 mid = left + (right−left)/2。看 nums[mid] 和 target 的关系，只分两种，不要先单独处理相等。
若 nums[mid] < target，中点这个数太小，它以及它左边都不可能是「第一个 ≥ target 的位置」。答案至少在 mid+1，令 left = mid+1。不变量的左半句仍然成立：left 左边都小于 target。若 nums[mid] ≥ target，中点已经够大，它可能就是答案，也可能答案更靠左。令 right = mid−1。不变量的右半句仍然成立：right 右边都大于等于 target。
主例走 target = 2。left=0, right=3, mid=1，nums[1]=3 ≥ 2，答案不会在 3 右边，right=0。只剩 nums[0]=1，1 < 2，left=1。此时 left=1 > right=0，区间空了，返回 1。把 2 插到下标 1，数组变成 [1, 2, 3, 5, 6]，仍然升序。
循环结束时一定有 left == right+1。left 左边全小于 target，left 以及右边全大于等于 target（如果 left == n，右边是空的，表示插到末尾）。所以返回 left，不要返回 mid：最后一轮的 mid 可能是一个已经确认太小或已经确认偏右的格子。也不要返回 right：right 停在最后一个小于 target 的位置，答案是它的下一格。
target 存在时：落在它自己的位置
同一套收缩覆盖「数在数组里」。nums = [1, 3, 5, 6]，target = 5。第一次 mid=1，nums[1]=3 < 5，3 及左边都太小，left=2。第二次 left=2, right=3, mid=2，nums[2]=5 ≥ 5，5 已经够大，right=1。left=2 > right=1，结束，返回 2。5 的下标就是 2。
注意：即使命中也不提前返回。相等被归进「大于等于」那一支，算法继续往左挤，直到挤到这一段 ≥ target 的最左边。本题元素互不相同，提前返回 mid 也对，但写成统一的「大于等于」更贴 lower_bound 这句话，三条文里的目标值走同一套收缩，插入和查找共用一个出口。
再走 target = 7，应插到末尾。三次比较都是中点太小：3 < 7 令 left=2，5 < 7 令 left=3，6 < 7 令 left=4。left 被推过数组末尾，停在 4，4 等于长度。target = 0 走相反方向：每次中点够大，right 被收到 −1，left 停在 0。空数组 right 一开始是 −1，循环不进，直接返回 left = 0。三种主例、最左插入、空数组都被同一句不变量覆盖。
七行 Go：lower_bound
func searchInsert(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid - 1}}return left}
1闭区间 [left, right]。循环条件 left <= right 表示区间里至少还有一个数。退出时 left == right+1。
2nums[mid] < target：mid 及左侧全太小，答案至少在 mid+1，令 left = mid+1。不变量左半句仍成立。
3否则 mid 已经够大，答案在 mid 或更左，令 right = mid−1。相等也走这一支，继续往左挤到第一个 ≥ target。
4返回 left，不要返回 mid 或 right。right 停在最后一个小于 target 的位置，答案是它的下一格，也就是 left。
总结
找第一个 ≥ target 的位置；守住左右不变量，区间空了就返回 left。
- 有序数组里「找到」和「插入」是同一个分界点。不要找「第一个大于」，等号必须留下，否则 target 在数组里会偏一格。
- nums[mid] < target 排除左半边，否则收右边界。left 左边都太小，right 右边都够大。
- 结束时返回 left 而非 −1，就是与 LC704 的唯一区别。返回 mid 或 right 会在三个主例里错两个。