如何用二分查找「最后一个等于目标值」的位置（右边界）？

简化版

找最后一个等于 target 的下标(右边界):遇到 a[mid] == target 时继续往右收缩(lo = mid+1),把可能更靠右的相等元素纳入,直到收敛。最简洁的做法是借助 upper_bound(第一个 > target 的位置)——右边界就是 upper_bound - 1。配合左边界,能 O(log n) 求出 target 的出现次数和区间。

详细版

// upper_bound：第一个 > target 的下标，左闭右开模板
int upperBound(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;  // <= target 都排除，往右收
        else hi = mid;                        // a[mid] > target，可能是答案
    }
    return lo;   // 第一个 > target 的位置
}

// 最后一个等于 target（右边界）
int findLast(int[] a, int target) {
    int i = upperBound(a, target) - 1;        // 右边界 = upper_bound - 1
    return (i >= 0 && a[i] == target) ? i : -1;
}

关键:把「等于」并入「小于」,a[mid] <= target 都 lo = mid+1(往右收),这样最终停在「第一个 > target」的位置。
右边界 = upper_bound − 1,再校验 a[i] == target。

完整版教学

一、右边界和左边界的对称性

找右边界(最后一个等于 target)和左边界(第一个等于 target)是镜像的:

左边界:相等时往左收(hi = mid),对应 lower_bound(第一个 ≥ target)。
右边界:相等时往右收(lo = mid+1),对应 upper_bound(第一个 > target) 减 1。

理解了对称性,两个边界就是一套模板的两种收缩方向,不用分别死记。

二、upper_bound 的语义

upperBound 返回「第一个 > target 的下标」。关键手法:把 a[mid] == target 和 a[mid] < target 合并成一个分支(a[mid] <= target 都 lo = mid+1),于是相等的元素全被「跳过」,最终停在第一个严格大于 target 的位置。

那么它的前一个位置(upper_bound - 1),如果值等于 target,就是最后一个等于 target(右边界)。
如果 upper_bound == 0 或 a[upper_bound-1] != target,说明 target 不存在。

三、为什么右边界要用「upper_bound − 1」而不是直接找

直接找右边界(相等时 lo = mid+1,记录 mid)也能写,但边界校验容易错(退出时 lo/hi 指向的含义要仔细推)。用 upper_bound − 1 更稳:upper_bound 是「第一个大于 target 的位置」,它左边一个自然是「≤ target 的最后一个」;如果那个值恰好 == target,就是右边界。这个转化把「找最后一个等于」变成了「找第一个大于再退一格」,逻辑清晰、不易错。

四、lower_bound 和 upper_bound 一起用:数出现次数

有了两个边界,一个经典应用是 O(log n) 求 target 在有序数组里出现了多少次:

int count(int[] a, int target) {
    int lo = lowerBound(a, target);   // 第一个 >= target
    int hi = upperBound(a, target);   // 第一个 > target
    return hi - lo;                    // 区间 [lo, hi) 全是 target
}

[lowerBound, upperBound) 这段区间里全是 target,长度就是出现次数。这比「找到一个再向两边线性扩展」(最坏 O(n))高效得多。LeetCode「在排序数组中查找元素的第一个和最后一个位置」就是这两个边界的组合。

五、走一个例子

a = [1, 2, 2, 2, 3]，找最后一个 2（右边界）：
upperBound 找第一个 > 2：
lo=0, hi=5
mid=2, a[2]=2 <= 2 → lo=3     [3,5)
mid=4, a[4]=3 > 2  → hi=4     [3,4)
mid=3, a[3]=2 <= 2 → lo=4     [4,4)
退出，upperBound=4（下标4是第一个>2的3）
右边界 = 4 - 1 = 3，a[3]=2==target ✓

六、复杂度与要点

时间 O(log n)。
要点:右边界相等时往右收(<= target 并入 lo=mid+1);用 upper_bound − 1 转化最稳;别忘了校验 a[i] == target 和下标越界(i >= 0)。

把问题转成 upper_bound 能统一相等分支：先找第一个严格大于 target 的位置 p，再检查 p-1。若 p=0 或 a[p-1] != target，说明目标不存在；这个验证能覆盖 target 小于最小值和落在相邻值之间两种情况。

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

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：先寻找第一个严格大于 target 的位置，再减一得到最后一个等于 target。

对应的状态推进是：当 a[mid]<=target 时向右保留答案候选，否则向左收缩。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

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

复杂度不能只背一个符号。upper_bound 为 O(log n)，最终等值验证仍不可省略。

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

核对项	结论
前提	适用于有序序列的末次出现与计数
时间复杂度	O(log n)
额外空间	O(1)
关键边界	结果减一可能为 -1；必须检查范围和 a[pos]==target
替代方案	左边界与右边界之差可计算出现次数

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

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

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

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“适用于有序序列的末次出现与计数”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“upper_bound 为 O(log n)，最终等值验证仍不可省略”。
误区：重复值和边界值不会改变代码。 结果减一可能为 -1；必须检查范围和 a[pos]==target。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“先寻找第一个严格大于 target 的位置，再减一得到最后一个等于 target”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[1,2,2,2,4] 的 upper_bound 是下标 4，右边界为 3”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“左边界与右边界之差可计算出现次数”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

找右边界(最后一个等于 target):相等时往右收(lo = mid+1),对应 upper_bound(第一个 > target),右边界 = upper_bound − 1(再校验 a[i]==target 且 i>=0)。它和左边界(lower_bound,相等往左收)是镜像。二者合用:出现次数 = upperBound − lowerBound(区间 [lower, upper) 全是 target),O(log n)。这就是「查找元素第一个和最后一个位置」的标准解法。

简化版

详细版