0034. Find First and Last Position of Element in Sorted Array

题目信息

题号:
  1. 在排序数组中查找元素的第一个和最后一个位置

难度:

Medium

主题:

数组、二分查找、边界定位

原题:

LeetCode 0034

重点:

从找到任意目标位置,推导到分别寻找第一个不小于目标和第一个大于目标的位置

题目重述

给定一个按非递减顺序排列的整数数组 nums 和整数 target,返回目标值第一次与最后一次出现的零基下标, 结果格式为 [first, last]。

若 target 不在数组中,返回 [-1, -1]。算法必须达到 O(log n) 时间复杂度。

nums 的长度位于 [0, 10^5],数组元素和 target 均位于 [-10^9, 10^9]。数组中允许存在 重复值;由于数组有序,所有等于 target 的元素必然构成一个连续区间。

自建示例

  • 重复段位于中间:nums = [1, 2, 2, 2, 2, 5, 8]、target = 2,返回 [1, 4];

  • 目标只出现一次:nums = [-3, 0, 4, 7]、target = 4,返回 [2, 2];

  • 整个数组都是目标:nums = [6, 6, 6, 6]、target = 6,返回 [0, 3];

  • 目标位于插入位置但并不存在:nums = [1, 3, 5, 7]、target = 4,返回 [-1, -1];

  • 空数组:nums = []、target = 9,返回 [-1, -1]。

C++ 实现

#include <vector>

class Solution {
private:
    std::vector<int> linearScan(const std::vector<int>& nums, int target) {
        int first = -1;
        int last = -1;
        for (int index = 0; index < static_cast<int>(nums.size()); ++index) {
            if (nums[index] < target) {
                continue;
            }
            if (nums[index] > target) {
                break;
            }
            if (first == -1) {
                first = index;
            }
            last = index;
        }
        return {first, last};
    }

    std::vector<int> binaryThenExpand(const std::vector<int>& nums, int target) {
        int low = 0;
        int high = static_cast<int>(nums.size()) - 1;
        int found = -1;
        while (low <= high) {
            const int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                found = mid;
                break;
            }
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        if (found == -1) {
            return {-1, -1};
        }

        int first = found;
        int last = found;
        while (first > 0 && nums[first - 1] == target) {
            --first;
        }
        while (last + 1 < static_cast<int>(nums.size()) && nums[last + 1] == target) {
            ++last;
        }
        return {first, last};
    }

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

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

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

public:
    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        return boundaryBinarySearch(nums, target);
    }
};

题解

线性扫描

最直接的方法从左到右检查数组。第一次遇到 target 时记录 first,之后每次遇到目标都更新 last。 数组有序,因此:

  • 当前值小于目标时继续向右;

  • 当前值等于目标时记录边界;

  • 当前值大于目标后,右侧只会更大,可以立即停止。

linearScan 准确表达了题目要求,也直接利用了目标值连续出现这一事实。不过当目标位于数组末尾或整个数组都等于 目标时,仍要读取 n 个元素,时间为 O(n),不能满足题目的对数要求。

普通二分与线性扩展

普通二分能够在 O(log n) 时间内找到某个等于 target 的位置,但遇到相等时立即返回,不能保证该位置是重复 段的左端或右端。

binaryThenExpand 先二分得到下标 found,再从这里分别向左和向右移动,直到相邻元素不再等于目标。 重复段长度为 r 时,扩展仍需要 O(r) 次操作。

若数组全部由目标值组成,二分虽然很快命中中间位置,随后仍要走到数组两端,总时间退化为 O(n)。瓶颈已经 从“寻找目标”转移到“逐个穿过重复段”,因此边界本身也必须通过二分直接定位。

单调边界条件

边界二分不再询问“中点是否等于目标”,而是寻找某个单调条件第一次成立的位置。

左边界对应:

nums[index] >= target

在有序数组中,这个条件沿下标方向呈现为一段 false 后跟一段 true。第一个成立的位置就是 lowerBound(target),即第一个不小于目标的下标。

右边界之后的位置对应:

nums[index] > target

第一个成立的位置是 upperBound(target),即第一个严格大于目标的下标。记它为 afterLast,重复段右端 就是 afterLast - 1。

直接搜索“严格大于”比搜索 target + 1 更准确,也不依赖整数加一,因此不会在目标达到整数上界时产生溢出。

半开区间不变量

lowerBound 与 upperBound 都在半开区间 [low, high) 中搜索,并允许答案等于 nums.size()。

对 lowerBound,循环始终保持:

  • [0, low) 中的值都严格小于 target;

  • [high, n) 中的位置都满足值不小于 target;

  • 第一个满足条件的位置仍位于 [low, high]。

若 nums[mid] < target,中点及其左侧都不满足条件,令 low = mid + 1。否则中点仍可能是第一个满足位置, 令 high = mid。当 low == high 时,唯一候选就是左边界。

upperBound 使用相同的区间结构,只把不满足条件的范围改为 nums[mid] <= target。所有相等元素会被排除到 左侧,搜索最终停在重复段之后。

目标区间

非递减顺序保证数组可以按目标值划分为:

小于 target | 等于 target | 大于 target

lowerBound 定位第二段起点,upperBound 定位第三段起点。若 lowerBound 越过数组,或该位置的值不等于 目标,第二段为空,答案就是 [-1, -1]。

目标存在时,两次边界之间的元素全部等于目标,所以答案直接为:

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

不需要再检查重复段中的任何元素。

状态演化

对 nums = [1, 2, 2, 2, 2, 5, 8]、target = 2:

搜索

low

mid

high

中点值

更新

lowerBound

0

3

7

2

high = 3

lowerBound

0

1

3

2

high = 1

lowerBound

0

0

1

1

low = 1,得到 first = 1

upperBound

0

3

7

2

low = 4

upperBound

4

5

7

5

high = 5

upperBound

4

4

5

2

low = 5,得到 afterLast = 5

最终区间为 [first, afterLast - 1] = [1, 4]。

代码演进

linearScan 逐个读取元素并直接维护首尾位置,正确但没有利用边界条件的单调性。

binaryThenExpand 用普通二分删除了寻找任意目标位置的线性工作,但向两侧扩展仍会逐个穿过重复段。它说明 “命中即停止”的二分语义太弱,必须让搜索继续逼近边界。

boundaryBinarySearch 分别寻找第一个 >= target 与第一个 > target 的位置,删除命中后的线性扩展。 公开入口采用该方法,两次搜索都只保留可能包含边界的一半区间。

复杂度分析

linearScan 的时间复杂度为 O(n)。binaryThenExpand 先用 O(log n) 找到一个目标,再用 O(r) 穿过长度为 r 的重复段,最坏仍为 O(n)。

边界方法执行两次二分,每次把搜索区间至少缩小一半,时间复杂度为 O(log n);只使用固定数量的下标变量, 额外空间为 O(1)。返回结果不计入工作空间。