题目描述
升序数组中找 target，存在返回下标；不存在返回它按序应插入的位置。
思路解析
挨个比当然能找到第一个 ≥ target 的位置，可那是 O(n)。数组明明是升序的，把这个条件用起来，就能砍到 O(log n)。
转折：升序数组里「nums[i] ≥ target」一旦成立，后面就全成立——这是一条单调的真/假分界。二分要找的就是这条分界的左端。不变量：始终保证答案落在 [l, r] 里——nums[mid] ≥ target 时答案可能就是 mid，所以收 r=mid（不减 1）；nums[mid] < target 时 mid 太小，l=mid+1。最后 l 就是答案。
准备 · 半开区间 [0,4)：这里 r 取 len=4（注意能等于长度，因为答案可能是「插在最末尾」）。l=0。要找第一个 ≥ 2 的位置。
第 1 轮 · 取 mid：中点 mid=2，nums[2] = 5。拿它和 target=2 比，决定收哪边。
第 1 轮 · 判断：5 ≥ 2，说明 mid=2 这个位置「满足条件」，它有可能就是答案，但右边更不可能是答案。所以收右边，但 r 收到 mid 而不是 mid−1（别把 mid 自己丢了）。
第 1 轮 · 收缩：r 收到 2，范围变成 [0, 2)。下标 2、3（灰）整段丢掉。注意 mid=2 虽是候选，但它右边的更大值不可能更优，所以一起丢。
第 2 轮 · 取 mid：范围 [0, 2)，新中点 mid=1，nums[1] = 3。
第 2 轮 · 判断：3 也 ≥ 2，下标 1 仍是候选。继续往左缩，r 收到 mid=1。
第 2 轮 · 收缩：r 收到 1，范围 [0, 1)，只剩下标 0 没判。
第 3 轮 · 取 mid（负例分支）：这轮是另一种分支：mid=0，nums[0]=1 比 target 小。1 排不到 2 前面，下标 0 不可能是插入位置。
第 3 轮 · 收缩 → l 越过：nums[mid] 太小，mid 及左边全丢，l 跳到 mid+1=1。现在 l == r == 1，区间空了，循环结束。
返回 l：收尾时 l = 1 就是答案：2 插在下标 1，数组变 [1,2,3,5,6] 仍升序。无论 target 在不在数组里，返回的都是 l。
只要能把问题变成「第一个满足某条件的位置」，就是 lower_bound：r=mid 留候选、l=mid+1 弃旧，最后返回 l。x 的平方根、第一个错误版本都是这个模板。
参考代码（Python）
1def searchInsert(self, nums, target):
2 l, r = 0, len(nums) # 半开区间 [l, r)，r 可等于 len
3 while l < r: # 注意是 < 不是 <=
4 mid = l + (r - l) // 2 # 取中点，防溢出
5 if nums[mid] >= target:
6 r = mid # mid 是候选，收 r=mid 不减 1
7 else:
8 l = mid + 1 # mid 太小，丢掉它
9 return l # 找不到也返回 l，就是插入位置复杂度分析
- 时间复杂度：O(log n) —— 每轮把搜索区间砍掉一半
- 空间复杂度：O(1) —— 只用 l、r、mid 三个变量
套路模板
三处要点：while l < r、r=mid 不减 1、返回 l。这套「找下界」模板比 ≤ 版更适合「找第一个满足条件的位置」。
1l, r = 0, len(nums) # 半开 [l, r)
2while l < r:
3 mid = l + (r - l) // 2
4 if check(mid): # nums[mid] >= target
5 r = mid # 留候选
6 else:
7 l = mid + 1 # 弃旧
8return l # 第一个满足的位置易错点
- 错误写法：找不到时返回 -1 → 正确写法：返回 l（就是插入位置）（本题求的是插入位置，不存在时 l 正好停在该插入的下标，返回 -1 是把它当普通查找做错了）
- 错误写法：nums[mid] >= target 时写 r = mid - 1 → 正确写法：r = mid（不减 1）（mid 自己可能就是第一个满足的位置，减 1 会把答案丢掉，导致结果偏小）
- 错误写法：r 初始化成 len(nums) - 1 → 正确写法：r = len(nums)（target 比所有数都大时插入位置是末尾 len，r 少 1 就够不到）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。