1、题目描述
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
2、问题描述：
- 给一个排好序的数组，给一个target，查找target起始位置，和最终位置。如果没有，那么返回-1， -1.
3、问题关键：
- 有序，一般二分查找，二分的两个模版，一个是求小于等于target的最大值，一个是大于等于target的最小值。
- 一般写二分的思考顺序是这样的：首先通过题目背景和check(mid)函数的逻辑，判断答案落在左半区间还是右半区间。
左右半区间的划分方式一共有两种： - 1.中点mid属于左半区间，则左半区间是[l, mid]，右半区间是[mid+1, r]，更新方式是r = mid;或者 l = mid + 1;，此时用第一个模板；
- 2.中点mid属于右半区间，则左半区间是[l, mid-1]，右半区间是[mid, r]，更新方式是r = mid - 1;或者 l = mid;，此时用第二个模板；
4、C++代码：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return vector<int>({-1, -1});
int n = nums.size();
vector<int> res;
int l = 0, r = n - 1;
while(l < r) {
int mid = l + r >> 1;//小于等于k的最大值。（答案在左边）
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] != target) return vector<int>({-1, -1});//不存在这个数。
res.push_back(l);
l = 0, r = n - 1;
while(l < r) {
int mid = l + r + 1 >> 1;//大于等于target的最小值。（答案在右边）
if (nums[mid] <= target) l = mid;
else r = mid - 1;
}
res.push_back(l);
return res;
}
};
