个人主页：Lei宝啊
愿所有美好如期而遇
目录
本题链接
输入描述
输出描述
算法分析
1.算法一：暴力求解
2.算法二：朴素二分算法
3.算法三：二分查找左右端点
3.1查找左端点
3.1.1细节一：循环条件
3.1.2细节二：mid的值
3.2查找右端点
解题源码
本题链接
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
输入描述
我们选择示例1，接口为vector<int> searchRange(vector<int>& nums, int target) ，向nums中写入非递减的数字，也就是说可以有多个重复的相同数字。
输出描述
由于nums中可能有多个值与target相等，所以我们需要记录这个区间的左端点和右端点，然后返回这个区间，如果找不到，则区间为[-1,-1]。
算法分析
1.算法一：暴力求解
直接从左到右扫描这个数组，通过begin和end变量来记录相等于target的起始位置和结束位置，找不到则返回[-1,-1]，时间复杂度为O(N)。
2.算法二：朴素二分算法
直接二分，如果寻找的target在nums中只有一个，那么时间复杂度为log(N)，但是如果有多个的话，我们还是需要去遍历mid的左边和mid的右边，如果整个数组所有值都与target相等，就相当于要遍历整个数组，时间复杂度仍然为O(N)，这里我们使用朴素二分算法仍然不是最优的。
3.算法三：二分查找左右端点
3.1查找左端点
我们可以将数组分成两个区间，以[5,7,7,8,8,10],target = 8为例，既然我们要找左端点，也就是最左边的那个8，所以我们将数组分成小于target的区间和大于等于target的区间，即[5,7,7] [8,8,10]这两个区间。(lhs意为left side hand即左手边，rhs意为right side hand即右手边)
我们定义一个mid，mid = lhs + (rhs - lhs) / 2，并且有两种结果：
- 当nums[mid] < target ，lhs = mid + 1;
- 当nums[mid] >= target, rhs = mid;
你可能会问，为什么rhs = mid, 按照我们朴素二分算法的理解，应该是rhs = mid - 1, 我们可以举个例子，如果说mid = 3,也就是上面最左边的8，那么再怎么样我们也无法找到左端点了。
同时按照我们上面的两种结果，我们也可以发现一个事实，就是rhs永远不会出他的区间，lhs是可以跨区间的，当lhs == rhs时，也就代表着循环结束了。
所以这就是全部了吗？当然不是，他还有其他细节，这些细节一但注意不到，就是一个接一个的死循环。
3.1.1细节一：循环条件
朴素二分算法循环条件是lhs <= rhs，那么我们这里也是这样吗？上面我们提过一个事实，就是说当lhs == rhs时就已经结束了，而且正好是我们的左端点，所以说我们不用再去判断相等的情况，你可能会说，碰巧罢了，你这是能找到结果，你要是找不到呢？如果nums里全部大于target呢？如果nums里全部小于target呢？那我们分三种情况:
所以我们不需要判断lhs == rhs这种情况，因为我们上述三种情况就是本题的所有情况，而我们也证实了当lhs == rhs时就是我们的结果，要么找到，要么就找不到。
但是有人会犯倔，我嫌麻烦，还得想这么多东西，不就多判断一次嘛？我就用lhs <= rhs， 有问题吗？还是分三种情况，运气好点就不死循环。
所以我们循环条件也有两个细节：
- 细节一：无需判断lhs == rhs，因为此时已经是结果了。
- 细节二： 如果真的比较了，可能会死循环，在leetcode众多测试用例中，一定是错的。
3.1.2细节二：mid的值
我们上面直接让mid = lhs + (rhs - lhs) / 2; 可能你也没有思考为什么，可不可以，事实上，在查找左端点时这样正好可以，但是放在查找右端点上就是死循环，那么右端点mid怎么算？
mid = lhs + (rhs - lhs + 1) / 2;那么我们把这个用在左端点上看看效果。
我们可以发现：
- 选择第一种方式，mid的值偏向于左边下标
- 选择第二种方式，mid的值偏向于右边下标
细节很多，不注意就死循环，但是我们不要死记硬背，要去理解，怎么样就死循环了，这才是我们该做的。
3.2查找右端点
查找右端点和查找左端点思路完全相同，只是有些细节不同，我们这里指出：
- 区间的划分：大于target的区间的小于等于target的区间
- mid的计算：mid = lhs + (rhs - lhs + 1) / 2;
剩下的就是一个模子了。
解题源码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int> v(2,-1);
if(nums.size() <= 0) return v;
//计算左端点
int lhs = 0, rhs = nums.size() - 1, mid = lhs + (rhs - lhs) / 2;
while(lhs < rhs)
{
//分区间
if(nums[mid] < target) lhs = mid + 1; //小于区间
else rhs = mid; //大于等于区间
mid = lhs + (rhs - lhs) / 2;
}
if(nums[rhs] == target) v[0] = rhs;
//计算右端点
lhs = 0, rhs = nums.size() - 1, mid = lhs + (rhs - lhs + 1) / 2;
while(lhs < rhs)
{
//分区间
if(nums[mid] > target) rhs = mid - 1; //大于区间
else lhs = mid; //小于等于区间
mid = lhs + (rhs - lhs + 1) / 2;
}
if(nums[rhs] == target) v[1] = rhs;
return v;
}
};
