跳至主要內容

在排序数组中查找元素的第一个和最后一个位置：lower_bound/upper_bound完整实现

老张2026/4/30大约 10 分钟

在排序数组中查找元素的第一个和最后一个位置：lower_bound/upper_bound完整实现

适读人群：Java 后端工程师、算法备考者 | 阅读时长：约 18 分钟 | 难度：⭐⭐

开篇故事

有一次我在做代码审查，同事写了一段业务代码，需要在一个有序集合里找出某个区间内所有满足条件的记录。他用了 Java 的 Collections.binarySearch，找到一个位置之后，往左右两边线性扫描来确定范围。

我问他："你知道这段代码的最坏时间复杂度是多少吗？"他算了一下，说："O(log n + k)，k 是结果集大小。"我说对，但是如果结果集很大，比如有一半的元素都满足条件，这就退化成了 O(n)。而实际上，只用纯粹的二分查找，定位左右边界都是 O(log n) 的。

这就是 lower_bound 和 upper_bound 的价值所在——精准定位区间的两个端点，时间复杂度都是 O(log n)，和结果集的大小完全无关。

LeetCode 34 是这类问题的经典代表。我一直觉得这道题比 704 更有价值，因为它逼着你真正理解二分的"定位"语义，而不只是"查找"语义。

一、题目解析

题目： 给定一个按照升序排列的整数数组 nums 和一个目标值 target，找出目标值在数组中的开始位置和结束位置。如果目标值不存在于数组中，返回 [-1, -1]。要求算法时间复杂度为 O(log n)。

示例一：

  • 输入：nums = [5,7,7,8,8,10]，target = 8
  • 输出：[3, 4]

示例二：

  • 输入：nums = [5,7,7,8,8,10]，target = 6
  • 输出：[-1, -1]

题目要求 O(log n)，这直接排除了线性扫描的思路，必须用两次二分分别找左右边界。

关键洞察：

  • 左边界 = 第一个等于 target 的位置 = 第一个 >= target 的位置（即 lowerBound(target)）
  • 右边界 = 最后一个等于 target 的位置 = 第一个 > target 的位置减一（即 upperBound(target) - 1）

如果 lowerBound(target) 指向的元素不等于 target，则 target 不存在。

二、解法一：两次独立二分（朴素写法）

思路分析

分别写两个函数：findFirst 找第一个等于 target 的位置，findLast 找最后一个等于 target 的位置。

两个函数都用二分，但更新条件不同：

  • findFirst：找到 nums[mid] == target 时不立即返回，而是记录这个位置，然后继续向左搜索（right = mid - 1）。
  • findLast：找到 nums[mid] == target 时记录这个位置，然后继续向右搜索（left = mid + 1）。

完整代码

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }

    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;      // 记录找到的位置
                right = mid - 1;   // 继续向左缩小，寻找更靠左的位置
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;      // 记录找到的位置
                left = mid + 1;    // 继续向右缩小，寻找更靠右的位置
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {5, 7, 7, 8, 8, 10};
        int[] result = sol.searchRange(nums, 8);
        System.out.println(result[0] + " " + result[1]); // 3 4

        result = sol.searchRange(nums, 6);
        System.out.println(result[0] + " " + result[1]); // -1 -1
    }
}

复杂度分析

  • 时间复杂度：O(log n)。两次二分，每次 O(log n)，总计 O(2 log n) = O(log n)。
  • 空间复杂度：O(1)。

三、解法二：基于 lower_bound/upper_bound 的优雅实现

思路分析

这种写法把两个问题统一成 lower_bound 和 upper_bound 两个基础操作，代码更简洁，语义更清晰，而且可以复用于很多其他问题。

定义：

  • lowerBound(target)：返回第一个 >= target 的下标，如果不存在返回 n。
  • upperBound(target)：返回第一个 > target 的下标，如果不存在返回 n。

有了这两个工具：

  • 左边界 = lowerBound(target)，但需要检查该位置是否真的等于 target
  • 右边界 = upperBound(target) - 1

等价关系：upperBound(target) = lowerBound(target + 1)，所以实际上只需要一个函数。

完整代码

public class Solution2 {
    /**
     * lower_bound：第一个 >= target 的下标
     * 使用左闭右开区间 [left, right)
     */
    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;  // nums[mid] >= target，mid 可能是答案
            }
        }
        return left;
    }

    /**
     * upper_bound：第一个 > target 的下标
     * 等价于 lowerBound(target + 1)
     */
    private int upperBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;  // nums[mid] > target，mid 可能是答案
            }
        }
        return left;
    }

    public int[] searchRange(int[] nums, int target) {
        int lb = lowerBound(nums, target);

        // 如果 lb == nums.length 或者 nums[lb] != target，说明不存在
        if (lb == nums.length || nums[lb] != target) {
            return new int[]{-1, -1};
        }

        int ub = upperBound(nums, target);
        return new int[]{lb, ub - 1};
    }

    public static void main(String[] args) {
        Solution2 sol = new Solution2();
        int[] nums = {5, 7, 7, 8, 8, 10};

        int[] r1 = sol.searchRange(nums, 8);
        System.out.println(r1[0] + " " + r1[1]); // 3 4

        int[] r2 = sol.searchRange(nums, 7);
        System.out.println(r2[0] + " " + r2[1]); // 1 2

        int[] r3 = sol.searchRange(nums, 6);
        System.out.println(r3[0] + " " + r3[1]); // -1 -1
    }
}

复杂度分析

  • 时间复杂度：O(log n)。调用两次二分查找。
  • 空间复杂度：O(1)。

四、解法三最优：单函数复用 + 完整边界验证

思路分析

进一步精简，利用 upperBound(target) = lowerBound(target + 1) 的等价性，只实现一个 lowerBound 函数，然后用它推导所有结果。

同时，我们来仔细推导为什么 lowerBound 的退出条件能保证正确性，以及如何从数学角度证明循环一定会终止。

循环终止证明： 每次循环，right - left 必然减少。

  • 若 nums[mid] < target：left = mid + 1，新的 right - left = right - (mid + 1) = right - mid - 1 < right - left（因为 mid >= left，所以 mid + 1 > left）。
  • 若 nums[mid] >= target：right = mid，新的 right - left = mid - left < right - left（因为 mid < right，由 mid = left + (right - left) / 2 且 right > left 保证）。

因此每次循环区间严格缩小，有限步内必然终止。

Mermaid 图：lower_bound 工作流程

完整代码

public class Solution3 {
    /**
     * lower_bound：第一个 >= target 的下标
     * 数学性质：循环不变量 —— target 如果存在，下标一定在 [left, right) 中
     */
    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public int[] searchRange(int[] nums, int target) {
        // 左边界：第一个 >= target 的位置
        int first = lowerBound(nums, target);

        // 如果不存在，直接返回
        if (first >= nums.length || nums[first] != target) {
            return new int[]{-1, -1};
        }

        // 右边界：第一个 > target 的位置 - 1
        // 等价于 lowerBound(target + 1) - 1
        int last = lowerBound(nums, target + 1) - 1;

        return new int[]{first, last};
    }

    /**
     * 进阶：计算 target 在数组中出现的次数（O(log n)）
     */
    public int countOccurrences(int[] nums, int target) {
        int first = lowerBound(nums, target);
        if (first >= nums.length || nums[first] != target) {
            return 0;
        }
        int next = lowerBound(nums, target + 1);
        return next - first;
    }

    /**
     * 进阶：找到最接近 target 的元素（O(log n)）
     */
    public int findClosest(int[] nums, int target) {
        int pos = lowerBound(nums, target);
        if (pos == 0) return nums[0];
        if (pos == nums.length) return nums[nums.length - 1];
        // 比较 pos-1 和 pos 哪个更接近 target
        return (target - nums[pos - 1] <= nums[pos] - target)
                ? nums[pos - 1] : nums[pos];
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        int[] nums = {5, 7, 7, 8, 8, 10};

        // 基本测试
        int[] r1 = sol.searchRange(nums, 8);
        System.out.println(r1[0] + " " + r1[1]); // 3 4

        // 出现次数
        System.out.println(sol.countOccurrences(nums, 7)); // 2
        System.out.println(sol.countOccurrences(nums, 8)); // 2
        System.out.println(sol.countOccurrences(nums, 6)); // 0

        // 最接近的元素
        int[] nums2 = {1, 3, 5, 7, 9};
        System.out.println(sol.findClosest(nums2, 6)); // 5 或 7（这里返回5，因为差值相等取左边）
    }
}

复杂度分析

  • 时间复杂度：O(log n)。两次调用 lowerBound，每次 O(log n)。
  • 空间复杂度：O(1)。

五、举一反三：同类题与模板应用

相关题目：

题号题目用法
35搜索插入位置直接返回 lowerBound(nums, target)
278第一个错误的版本lowerBound 变种，条件改为 isBadVersion(mid)
658找到 K 个最接近的元素用 lowerBound 定位起点，再用双指针扩展
1060有序数组中的缺失元素二分查找配合计数
441排列硬币在答案空间上用 lowerBound 变种

核心模板（工业级实用版）：

// 在有序数组中统计 target 出现次数——O(log n)
int count = lowerBound(nums, target + 1) - lowerBound(nums, target);

// 在有序数组中找最后一个 <= target 的位置
int pos = lowerBound(nums, target + 1) - 1;

// 在有序数组中找第一个 >= target 的位置
int pos2 = lowerBound(nums, target);

六、踩坑实录

坑一：lowerBound 返回值没有做合法性检查

lowerBound(nums, target) 返回第一个 >= target 的位置，如果所有元素都小于 target，它会返回 nums.length，这是一个越界位置。我曾经直接用返回值做 nums[lowerBound(...)]，结果 ArrayIndexOutOfBoundsException。

正确做法：返回后必须先检查 pos < nums.length && nums[pos] == target。

坑二：target + 1 溢出问题

lowerBound(nums, target + 1) 这种写法，当 target == Integer.MAX_VALUE 时，target + 1 会溢出变成 Integer.MIN_VALUE，导致完全错误的结果。更稳健的写法是直接实现一个 upperBound 函数，用 nums[mid] <= target 作为条件，不依赖 target + 1。

坑三：认为两次二分中间可以短路优化

有人说，找到左边界之后，如果 nums[lb] != target，右边界也不存在，所以可以直接返回 [-1, -1]，这个判断是正确的。但反过来不成立——找到左边界不等于 target，不意味着数组里没有比 target 更大的元素。不能因为"优化"就跳过第二次二分，必须先验证左边界的有效性。

坑四：把 lowerBound 和 upperBound 的比较条件搞反

lowerBound 的更新条件是 nums[mid] < target 时 left = mid + 1； upperBound 的更新条件是 nums[mid] <= target 时 left = mid + 1。

区别就是 < 和 <=，一字之差，语义完全不同。我刚开始总是搞混。现在的记忆方法是：lowerBound 想找第一个不小于目标的位置，所以遇到"小于"就往右走；upperBound 想找第一个大于目标的位置，遇到"小于等于"都往右走。

坑五：在空数组上调用二分

nums = [] 时，lowerBound 中 left = 0, right = 0，循环条件 left < right 直接为假，返回 0。然后 0 >= nums.length（因为 nums.length == 0），所以返回 [-1, -1]，这是正确的。但如果你用了左闭右闭模板，right = -1，left = 0，left <= right 为假，也是正确的。两种写法对空数组都能处理，但要确认自己的写法经过了空数组验证。

七、总结

这道题是二分查找"定位"能力的核心体现。把它做透了，你就掌握了二分查找最实用的两个原语：lower_bound 和 upper_bound。

几个关键结论：

  1. 右边界 = upperBound(target) - 1 = lowerBound(target + 1) - 1，但要防止 target + 1 溢出。
  2. lowerBound 返回值范围是 [0, n]，必须检查合法性。
  3. 只要掌握了 lowerBound，几乎所有与"有序数组中定位"相关的问题都能用它来解决。

在工程实践中，Java 的 Arrays.binarySearch 在找不到元素时会返回 -(insertion point) - 1，这个设计其实就是在表达 lowerBound 的语义，只不过用了一种特殊的编码方式。理解了 lowerBound，也就理解了 Java 标准库的这个设计。

编辑此页
最近更新:
贡献者: xiaozhangge