力扣34. 在排序数组中查找元素的第一个和最后一个位置
题目：
34. 在排序数组中查找元素的第一个和最后一个位置
难度中等2187收藏分享切换为英文接收动态反馈
给你一个按照非递减顺序排列的整数数组 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
第一种错法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(!nums.size())return {-1,-1};
int first,last;
first = searchFirst(nums,target);
last = searchLast(nums,target);
if(first==-1)return {-1,-1};
else return {first,last};
}
int searchFirst(vector<int>& nums,int target){
int right,left,mid;
right = nums.size()-1,left=0;
while(right>left){
mid = (right + left)>>1;
if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}else{
right = mid;
}
}
if(nums[left]==target)return left;
else return -1;
}
int searchLast(vector<int>& nums,int target){
int right,left,mid;
right = nums.size()-1,left=0;
while(right>left){
mid = (right + left )>>1;//这里错了
if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}else{
left = mid;
}
}
return left;
}
};
因为这里searchLast是为了找这段连续数字的末尾的位置，应该要取右边界，就是向上取整，所以不能mid = (right + left )>>1，而是要mid = (right + left +1)>>1
，不然会陷入无限循环；
第一种对法：
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(!nums.size())return {-1,-1};
int first,last;
first = searchFirst(nums,target);
last = searchLast(nums,target);
if(first==-1)return {-1,-1};
else return {first,last};
}
int searchFirst(vector<int>& nums,int target){
int right,left,mid;
right = nums.size()-1,left=0;
while(right>left){
mid = (right + left)>>1;
if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}else{
right = mid;
}
}
if(nums[left]==target)return left;
else return -1;
}
int searchLast(vector<int>& nums,int target){
int right,left,mid;
right = nums.size()-1,left=0;
while(right>left){
mid = (right + left + 1)>>1;
if(nums[mid]>target){
right = mid - 1;
}else if(nums[mid]<target){
left = mid + 1;
}else{
left = mid;
}
}
return left;
}
};
searchFirst是向下取整，取左边界，searchLast是向上取整，取右边界
