给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路
- 执行 2 次二分查找，第一次查找第一个位置，第二次查找第二个位置
- 第一次查找 first，mid 找到后，往左区间继续查找直到找到第一个位置 first，注意与普通二分查找不同的是找到后 while 循环也不结束，直到 left > right
- 第二次查找 last 同理，往右区间查找
学习点
注意二分查找的 while 循环边界条件： * 之前解答中为 while (left < right - 1)，因为在循环中 left = mid, right = mid，而 mid 已经验证过不等于 target
- 这里为
while (left <= right)，因为在循环中left = mid + 1, right = mid - 1，left和right没有验证是否等于target，所以在最后一次循环left = right时，验证mid(=left=right)位置是否等于target
代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// empty
if (nums.size() == 0)
{
return vector<int> {-1, -1};
}
vector<int> res(2);
int left = 0;
int right = nums.size() - 1;
// 提前赋值
int first = -1;
int last = -1;
// 分两次查找
// 查找第一个
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
first = mid;
// 往左边找，找到第一个位置
right = mid - 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
// 查找第二个
left = 0;
right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target)
{
last = mid;
// 往右边找，找到最后一个位置
left = mid + 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
res[0] = first;
res[1] = last;
return res;
}
};
