跳到主要内容

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

本节目标

用两个边界二分定位有序数组中目标值的完整连续区间。

这道题使用二分查找解题框架中的边界抽象：不逐个向两侧扫描，而是分别寻找两个插入位置。

查看原题

题意与约束​

在非递减数组中返回 target 出现的起止下标；不存在时返回 [-1, -1]。重复元素形成连续区间。

朴素思路与瓶颈​

线性扫描可以记录第一次和最后一次出现的位置，但目标位于数组末尾或不存在时仍需检查全部元素。即使先二分命中一个目标，再向两侧逐个扩展，目标重复 n 次时也会退化为 O(n)，所以两个边界都应独立二分。

两个边界​

lowerBound(target) 返回第一个 >= target 的位置，upperBound(target) 返回第一个 > target 的位置。若目标存在，答案就是：

[lowerBound(target), upperBound(target) - 1]

边界函数并不承诺目标存在。它始终返回 [0, n] 中的合法插入位置，调用方只需检查左边界没有越界且对应值等于 target。右边界直接比较 >，不使用 target + 1，所以不会在整数边界溢出。

代码实现​

两个函数都在半开区间中把“满足条件”的中点及右侧候选保留下来，直到收敛到第一个满足位置。

C++17
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        const int first = lowerBound(nums, target);
        const int afterLast = upperBound(nums, target);
        if (first == static_cast<int>(nums.size()) || nums[first] != target) {
            return {-1, -1};
        }
        return {first, afterLast - 1};
    }

private:
    int lowerBound(const vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size());
        while (left < right) {
            const int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    int upperBound(const vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size());
        while (left < right) {
            const int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

复杂度分析​

  • 时间复杂度：O(log n)，进行两次二分。
  • 空间复杂度：O(1)，不计返回数组。

易错点​

  • 只检查 lowerBound 的位置，不检查是否等于目标，会把插入点误当答案。
  • 右端应为 upperBound - 1，不是 upperBound。
  • 全部元素相等时，两个边界仍分别落在 0 和 n。

模式迁移​

“第一个满足条件的位置”也直接解决搜索插入位置，并可迁移到单调谓词的二分答案问题。