如何用二分查找目标值的插入位置？lower_bound 和 upper_bound 有什么区别？

简化版

「搜索插入位置」就是找 target 应该插入到有序数组的哪个下标(保持有序)。答案正是 lower_bound——第一个 ≥ target 的位置:target 存在就返回它的位置,不存在就返回它该插入的位置。lower_bound 是「第一个 ≥ target」,upper_bound 是「第一个 > target」,两者只差在「相等时算不算」——这个细微差别决定了插入到重复元素的前面还是后面。

详细版

// 搜索插入位置 = 第一个 >= target 的下标（lower_bound）
int searchInsert(int[] a, int target) {
    int lo = 0, hi = a.length;        // 左闭右开
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;  // 严格小于才排除
        else hi = mid;                       // >= target，往左收
    }
    return lo;   // target 该插入的位置
}

lower_bound vs upper_bound:

	lower_bound	upper_bound
语义	第一个 ≥ target	第一个 > target
判断	`a[mid] < target` 才右移	`a[mid] <= target` 就右移
target 存在时返回	第一个等于的位置	最后一个等于的下一个位置
用于插入	插到相等元素前面	插到相等元素后面

完整版教学

一、搜索插入位置的本质

给一个有序数组和 target,要返回「把 target 插进去后仍保持有序」的下标。分析一下:

如果 target 存在,插到它(第一个相等元素)的位置就行。
如果 target 不存在,应该插到「第一个比它大的元素」前面。

两种情况合起来,就是「第一个 ≥ target 的位置」——正是 lower_bound。所以搜索插入位置的答案直接就是 lower_bound,不需要额外处理。这也说明 lower_bound 这个「第一个 ≥ target」的语义有多通用。

二、为什么 lower_bound 同时覆盖「找到」和「没找到」

lower_bound 的返回值在四种情况下都正确:

存在且唯一:返回它的位置(插在原位)。
存在且重复:返回第一个相等的位置(左边界)。
不存在:返回第一个比它大的位置(该插入处)。
比所有元素都大:返回 a.length(插到末尾)。

一个函数搞定所有情况,这是它优雅的地方。搜索插入位置就是它的直接应用。

三、lower_bound 和 upper_bound 的唯一区别

两者代码几乎一样,唯一区别在相等时怎么处理:

lower_bound:a[mid] < target 才 lo = mid+1——相等时往左收(hi = mid),所以停在第一个相等元素(≥ 的第一个)。
upper_bound:a[mid] <= target 就 lo = mid+1——相等时往右收,所以跳过所有相等元素,停在第一个大于的位置。

记忆:lower 用 <(相等留下往左),upper 用 <=(相等跳过往右)。就这一个符号的差别,决定了是「第一个 ≥」还是「第一个 >」。

四、两者的配合与实际意义

插入到重复元素的前 or 后:如果要让新元素插到相等元素前面,用 lower_bound;插到后面,用 upper_bound。
区间定位:[lower_bound(x), upper_bound(x)) 恰好是所有等于 x 的元素区间,长度是 x 的出现次数。
标准库:C++ STL 的 lower_bound/upper_bound、Java 的 Arrays.binarySearch(但它对重复元素返回任意一个,不保证边界,要边界还得自己写)都是这套。

五、注意 Arrays.binarySearch 的坑

Java 内置的 Arrays.binarySearch:

找到:返回某个匹配下标(重复元素时不保证是第一个或最后一个)。
没找到:返回 -(插入点) - 1(一个负数),插入点 = 该插入的位置。要用 -(ret) - 1 还原插入点。

所以如果需要「左/右边界」或干净的「插入位置」,别直接依赖 Arrays.binarySearch,自己写 lower_bound 更清晰可控。这是面试和工程常见的坑。

六、复杂度与应用

时间 O(log n)。
应用:搜索插入位置、有序数组插入维护、统计出现次数、离散化(把值映射到排名)、区间查询定位边界。

插入位置允许等于 n，这是半开区间写法的自然终点，不应强行截成 n-1。若数组含重复值，lower_bound 把新值插在所有相等值之前；若业务要求插到相等值之后，则应改用 upper_bound。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：答案是第一个大于等于 target 的位置，即 lower_bound。

对应的状态推进是：a[mid]>=target 时保留 mid 向左，否则把 lo 移到 mid+1。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。O(log n)，半开区间 [0,n) 自然允许答案为 n。

带数字走一遍：[1,3,5,6] 查 2 返回 1，查 7 返回 4。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	输入必须有序；相等元素存在时返回第一处插入位置
时间复杂度	O(log n)
额外空间	O(1)
关键边界	不要把“找到任意 target”直接返回，否则重复值时语义变化
替代方案	upper_bound 返回第一个严格大于 target 的位置

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“输入必须有序；相等元素存在时返回第一处插入位置”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“O(log n)，半开区间 [0,n) 自然允许答案为 n”。
误区：重复值和边界值不会改变代码。 不要把“找到任意 target”直接返回，否则重复值时语义变化。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“答案是第一个大于等于 target 的位置，即 lower_bound”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[1,3,5,6] 查 2 返回 1，查 7 返回 4”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“upper_bound 返回第一个严格大于 target 的位置”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

搜索插入位置 = lower_bound(第一个 ≥ target)——存在返回其位置、不存在返回该插入处、超范围返回 a.length,一个函数覆盖所有情况。lower_bound(第一个 ≥,a[mid]<target 才右移,相等往左) vs upper_bound(第一个 >,a[mid]<=target 就右移,相等往右),只差一个 </<=,决定插到重复元素前/后。[lower, upper) 是相等元素区间。注意 Java Arrays.binarySearch 不保证边界、没找到返回 -(插入点)-1。

简化版

详细版