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

简化版

数组里 target 可能重复出现,要找第一个等于 target 的下标(左边界)。技巧:找到 a[mid] == target 时别急着返回,而是继续往左收缩(hi = mid),把可能更靠左的相等元素也纳入搜索;直到区间收敛。本质是「找第一个 ≥ target 的位置(lower_bound),再看它是不是等于 target」。

详细版

// 找第一个 >= target 的下标（lower_bound），左闭右开模板
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;       // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;   // mid 太小，排除
        else hi = mid;                        // a[mid] >= target，可能是答案，往左收
    }
    return lo;   // 第一个 >= target 的位置（可能等于 a.length）
}

// 找「第一个等于 target」：在 lowerBound 基础上校验
int findFirst(int[] a, int target) {
    int i = lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

关键:a[mid] >= target 时收 hi = mid(不是 mid-1),不放过 mid,继续向左找更早的相等位置。
退出时 lo == hi 指向「第一个 ≥ target」的位置。
再校验 a[lo] == target 才确认是「第一个等于」;否则 target 不存在。

完整版教学

一、为什么基础二分找不了边界

基础二分一遇到 a[mid] == target 就 return mid,但重复元素时,这个 mid 可能在中间,不是第一个。比如 [1, 2, 2, 2, 3] 找 2,基础二分可能返回下标 2,但第一个 2 在下标 1。要找边界,必须在相等时不停下,继续朝边界方向收缩。

二、核心思路:相等时继续向左

找左边界(第一个等于 target),思路是:当 a[mid] == target 时,记录下来但继续往左找——因为左边可能还有相等的。收缩用 hi = mid,把右半(含 mid 右边)排除,继续在左半(含 mid)搜。这样最终会停在最左边的相等位置。

把「相等」和「大于」合并成一个分支(a[mid] >= target 都往左收),就得到了 lower_bound——第一个 ≥ target 的位置,它天然就是左边界的位置。

三、lower_bound 的语义

lowerBound 返回「第一个 ≥ target 的下标」,这个语义非常有用,涵盖多种情况:

target 存在且有重复 → 返回第一个等于 target 的位置(左边界)。
target 存在且唯一 → 返回它的位置。
target 不存在 → 返回第一个比 target 大的位置(即 target 应该插入的位置)。
target 比所有元素都大 → 返回 a.length(数组末尾之后)。

所以拿到 lower_bound 的结果后,校验 a[i] == target 就能判断 target 在不在、以及左边界在哪。

四、为什么用 `hi = mid` 而不是 `mid-1`

这是找边界和基础二分的关键区别。基础二分排除 mid 用 mid±1,因为它确定 mid 不是答案。但找左边界时,a[mid] == target 的 mid 可能就是答案(如果左边没有更早的),不能直接排除掉。所以用 hi = mid——保留 mid 在下一轮的可能候选里(左闭右开区间 [lo, mid) 实际把 mid 排出了检查,但 lo 侧仍可能收敛到 mid)。配合左闭右开模板 while lo < hi,退出时 lo == hi 恰好是答案。

五、走一个例子

a = [1, 2, 2, 2, 3]，找第一个 2：
lo=0, hi=5
mid=2, a[2]=2 >= 2 → hi=2      区间[0,2)
mid=1, a[1]=2 >= 2 → hi=1      区间[0,1)
mid=0, a[0]=1 < 2  → lo=1      区间[1,1)
lo==hi=1，退出。a[1]=2==target ✓ 左边界是下标 1

每次相等都往左收,最终停在最左的 2。

六、复杂度与应用

时间 O(log n):仍是二分,每步减半。
应用:统计 target 出现次数(右边界 − 左边界 + 1)、有序数组去重定位、Arrays/STL 的 lower_bound、范围查询的起点定位。

若同时求左右边界，应分别做两次独立的边界二分，总时间仍是 O(log n)，因为常数 2 不改变渐进阶。返回下标前必须先检查它小于 n 且值等于 target，否则 lower_bound 只是插入位置，不代表目标真实存在。

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

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：区间始终保留第一个大于等于 target 的候选位置。

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

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

复杂度不能只背一个符号。O(log n)，结果是 lower_bound；返回后还需检查是否真的等于 target。

带数字走一遍：[1,2,2,2,4] 查 2 最终停在下标 1，而不是任意一个 2。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	适用于有序序列的首次出现和插入位置
时间复杂度	O(log n)
额外空间	O(1)
关键边界	半开区间 hi=n 可表示插到末尾；验证等值前先检查下标未越界
替代方案	只求任意命中可用基础二分

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

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

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

八、常见误区与追问

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

九、加强记忆

找左边界(第一个等于 target)= lower_bound(第一个 ≥ target) + 校验。核心:a[mid] == target 时不返回,继续往左收 hi = mid(保留 mid 为候选,别用 mid-1),把「等于」和「大于」合并成 >= target 往左收。退出时 lo==hi 是「第一个 ≥ target」的位置,再验 a[lo]==target。O(log n)。lower_bound 还兼「target 应插入的位置」,配右边界可数出现次数。

简化版

详细版