别再手写各种二分查找了！一个函数搞定所有边界问题

在算法竞赛或日常开发中，你是否经常遇到这些需求？

找第一个 ≥ x 的位置
找最后一个 ≤ x 的元素
查询某个值出现的次数
判断某个值是否存在

很多人会为每种情况单独写一个二分模板，结果不是死循环，就是边界出错。其实，你只需要一个可靠的 lowerBound 函数，就能推导出所有答案！

在此我分享一个我长期使用的、基于 while (l <= r) 风格的 lowerBound 实现，以及如何用它“一招鲜，吃遍天”。

🔧 核心函数：`lowerBound`

// 返回第一个 >= x 的下标；如果不存在，返回 n（表示“插入位置”）
public static int lowerBound(int[] a, int x) {
    int n = a.length;
    int l = 0, r = n - 1;
    int result = n; // 默认：没找到，返回 n
    while (l <= r) {
        int mid = l + (r - l) / 2; // 相当于 (l + r) / 2，但可以避免加法溢出
        if (a[mid] >= x) {
            result = mid;      // 候选答案
            r = mid - 1;       // 继续往左找更小的满足者
        } else {
            l = mid + 1;
        }
    }
    return result;
}

✨ 为什么这个写法好？

使用 while (l <= r)，符合闭区间直觉，不会死循环
每次都跳过 mid（l = mid + 1 或 r = mid - 1），无需 +1 技巧
通过 result 显式记录答案，天然支持“无解”情况
返回 n 表示“应插入的位置”，与 C++ STL、Python bisect 行为一致

🧩 万能组合：用 `lowerBound` 推导一切

假设数组 a 已升序排序，长度为 n。

需求	实现方式	原理说明
第一个 ≥ x 的位置	`pos = lowerBound(a, x)`	直接调用
第一个 > x 的位置	`pos = lowerBound(a, x + 1)`	`>x` ⇔ `≥(x+1)`（整数）
最后一个 ≤ x 的位置	`pos = lowerBound(a, x + 1) - 1`	第一个 `>x` 的前一个
最后一个 < x 的位置	`pos = lowerBound(a, x) - 1`	第一个 `≥x` 的前一个
x 的出现次数	`count = lowerBound(a, x + 1) - lowerBound(a, x)`	右边界 - 左边界
是否存在 x	`int p = lowerBound(a, x); return p < n && a[p] == x;`	先找位置，再验证

💡 这些变换在 LeetCode 34（查找元素范围）、计数问题、离散化 等场景中极其常用。

🌰 实战：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

题目链接

public int[] searchRange(int[] nums, int target) {
    int left = lowerBound(nums, target);
    int right = lowerBound(nums, target + 1) - 1;
  
    if (left <= right) {
        return new int[]{left, right};
    }
    return new int[]{-1, -1};
}

✅ 仅两行核心逻辑，清晰、高效、无 bug！