0034. Find First and Last Position of Element in Sorted Array
============================================================
题目信息
--------
:题号: 0034. 在排序数组中查找元素的第一个和最后一个位置
:难度: 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++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
std::vector linearScan(const std::vector& nums, int target) {
int first = -1;
int last = -1;
for (int index = 0; index < static_cast(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 binaryThenExpand(const std::vector& nums, int target) {
int low = 0;
int high = static_cast(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(nums.size()) && nums[last + 1] == target) {
++last;
}
return {first, last};
}
int lowerBound(const std::vector& nums, int target) {
int low = 0;
int high = static_cast(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& nums, int target) {
int low = 0;
int high = static_cast(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 boundaryBinarySearch(const std::vector& nums, int target) {
const int first = lowerBound(nums, target);
if (first == static_cast(nums.size()) || nums[first] != target) {
return {-1, -1};
}
const int afterLast = upperBound(nums, target);
return {first, afterLast - 1};
}
public:
std::vector searchRange(std::vector& 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)``。瓶颈已经
从“寻找目标”转移到“逐个穿过重复段”,因此边界本身也必须通过二分直接定位。
单调边界条件
~~~~~~~~~~~~
边界二分不再询问“中点是否等于目标”,而是寻找某个单调条件第一次成立的位置。
左边界对应:
.. code-block:: text
nums[index] >= target
在有序数组中,这个条件沿下标方向呈现为一段 ``false`` 后跟一段 ``true``。第一个成立的位置就是
``lowerBound(target)``,即第一个不小于目标的下标。
右边界之后的位置对应:
.. code-block:: text
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``。所有相等元素会被排除到
左侧,搜索最终停在重复段之后。
目标区间
~~~~~~~~
非递减顺序保证数组可以按目标值划分为:
.. code-block:: text
小于 target | 等于 target | 大于 target
``lowerBound`` 定位第二段起点,``upperBound`` 定位第三段起点。若 ``lowerBound`` 越过数组,或该位置的值不等于
目标,第二段为空,答案就是 ``[-1, -1]``。
目标存在时,两次边界之间的元素全部等于目标,所以答案直接为:
.. code-block:: text
[lowerBound(target), upperBound(target) - 1]
不需要再检查重复段中的任何元素。
状态演化
~~~~~~~~
对 ``nums = [1, 2, 2, 2, 2, 5, 8]``、``target = 2``:
.. list-table::
:header-rows: 1
* - 搜索
- ``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)``。返回结果不计入工作空间。