34. 在排序数组中查找元素的第一个和最后一个位置
一句话套路两次边界:lower_bound 与 upper_bound
题目描述
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
示例 3:
输入:nums = [], target = 0 输出:[-1,-1]
提示:
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
思路
时间
O(log n)空间
O(1)思路
两次「找边界」。first = lower_bound(target),last = lower_bound(target+1) - 1。找右边界也可以写成 upper_bound。
这就是「target 的取值范围 = [lower_bound(t), upper_bound(t))」。
提醒
target 可能不存在(要判 *it != target),也可能在末尾(+1 会溢出,所以手写时找右边界用 upper_bound 语义而不是 target+1)。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0034 {
class Solution {
public:
// 手写边界版:第一个 >= target 的下标(等于 nums.size() 表示没有)
static int lowerBound(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size(); // 半开区间 [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] < target)
lo = mid + 1;
else
hi = mid; // mid 可能就是答案
}
return lo;
}
// 第一个 > target 的下标。用 upperBound 而不是 lowerBound(target+1):
// 后者在 target == INT_MAX 时会整型溢出(这是本题最阴的坑)。
static int upperBound(const vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] <= target)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
vector<int> searchRange(const vector<int>& nums, int target) {
int first = lowerBound(nums, target);
if (first == (int)nums.size() || nums[first] != target) return {-1, -1};
return {first, upperBound(nums, target) - 1};
}
// STL 版:一行搞定,写业务代码时优先用它
static vector<int> searchRangeSTL(const vector<int>& nums, int target) {
auto lo = std::lower_bound(nums.begin(), nums.end(), target);
if (lo == nums.end() || *lo != target) return {-1, -1};
auto hi = std::upper_bound(lo, nums.end(), target);
return {(int)(lo - nums.begin()), (int)(hi - nums.begin()) - 1};
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0034::Solution s;
vector<int> a{5, 7, 7, 8, 8, 10};
CHECK_EQ(s.searchRange(a, 8), vector<int>{3, 4});
CHECK_EQ(s.searchRange(a, 6), vector<int>{-1, -1});
CHECK_EQ(s.searchRange(std::vector<int>{}, 0), vector<int>{-1, -1});
vector<int> b{1};
CHECK_EQ(s.searchRange(b, 1), vector<int>{0, 0});
vector<int> c{2, 2}; // 全部相同
CHECK_EQ(s.searchRange(c, 2), vector<int>{0, 1});
// 手写版与 STL 版必须完全一致
vector<int> d{1, 1, 1, 2, 3, 3, 4, 4, 4, 4};
for (int t = 0; t <= 5; ++t) CHECK_EQ(s.searchRange(d, t), s.searchRangeSTL(d, t));
vector<int> e{INT_MAX - 1, INT_MAX, INT_MAX}; // 验证不会因 target+1 溢出
CHECK_EQ(s.searchRange(e, INT_MAX), vector<int>{1, 2});
vector<int> f{INT_MIN, INT_MIN};
CHECK_EQ(s.searchRange(f, INT_MIN), vector<int>{0, 1});