分析
-
寻找左边界：
- 目标是找到
target 在数组中的最左侧位置
- 每次检查
nums[mid]是否大于等于 target
- 如果是，则缩小右边界
r = mid，以确保找到第一个出现的目标值
- 如果左边界不存在（即数组中没有
target），直接返回 [-1, -1]
-
寻找右边界：
- 目标是找到
target 在数组中的最右侧位置
- 每次检查
nums[mid] 是否小于等于 target
- 如果是，则缩小左边界
l = mid，确保找到最后一个出现的目标值
- 只有在左边界存在时，才会继续找右边界
时间复杂度
每次二分查找的时间复杂度为 O(log n)，总共两次，因此时间复杂度为 O(log n)
空间复杂度
空间复杂度为 O(1)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
vector<int> searchRange(vector<int>& nums, int target)
{
// 如果数组为空，直接返回
if (nums.empty())
return {-1, -1};
// 第一次二分查找左边界
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r) >> 1; // 中间位置
if (target <= nums[mid])
r = mid; // 缩小右边界
else
l = mid + 1; // 缩小左边界
}
// 检查左边界是否存在
if (nums[r] != target)
return {-1, -1};
int L = r; // 记录左边界
// 第二次二分查找右边界
l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1; // 中间位置，偏向右
if (target >= nums[mid])
l = mid; // 缩小左边界
else
r = mid - 1; // 缩小右边界
}
// 返回左右边界
return {L, r};
}
|
