34 在排数组中查找元素第一个和最后一个位置
原题地址：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
题目描述
给定一个按照升序排列的整数数组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]
分析
看到题目要求O(log n)就可以想到要用二分法
一开始做的时候思路比较low，想到使用二分法找到目标值后对其左右两侧分别使用线性查找边界。
实际上题目是想让作题者使用特殊的二分查找，通过改变二分的判断条件 来对左右边界实现二分查找
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int right =nums.size()-1;
int left=0,mid=0;
int pos=0;//判断是否存在
vector<int> ans(2,0);
if(right==0)
{
if(target==nums[0])
return ans;
ans[0]=-1;
ans[1]=-1;
return ans;
}
while(right>=left)//二分判断条件一定注意是 >=
{ mid=(right+left)/2;
if(nums[mid]==target)
{
pos=1;
break;
}else if(nums[mid]>target)
{
right=mid-1;
}else
{
left=mid+1;
}
}
if (pos==0)
{
ans[0]=-1;
ans[1]=-1;
return ans;
}
int n= mid;
while(n>0 && nums[n-1]==target )//向左
{
n=n-1;
}
ans[0]=n;
n=mid;
while(n<nums.size()-1 && nums[n+1]==target)//向右
{
n=n+1;
}
ans[1]=n;
return ans;
}
};
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left =getLeftBorder(nums,target);
int right=getRightBorder(nums,target);
if(left ==-2||right==-2)
return {-1,-1};
if (right-left>1)//判断左右边界是否正确
return {left+1,right-1};
return {-1,-1};
}
//二分查找右边界
int getRightBorder(vector<int>&nums ,int target)
{
int left =0;
int right =nums.size() -1;
int rightBorder =-2;
while(left<=right)
{
int mid= left +(right-left)/2;
if(nums[mid] >target){
right =mid-1;
}else{ //找右侧的最左边边界即为 右边界 <=
left =mid+1;
rightBorder=left;
}
}
return rightBorder;
}
//二分查找左边界
int getLeftBorder(vector<int>&nums,int target)
{
int left =0;
int right =nums.size()-1;
int leftBorder = -2;
while(right>=left)
{
int mid=left+(right-left)/2;
if(nums[mid]<target)
{
left =mid+1;
}
else{ //找左侧的最右边边界即为 左边界 >=
right=mid -1;
leftBorder = right;
}
}
return leftBorder;
}
};