题目描述
给出一个有序数组，请在数组中找出目标值的起始位置和结束位置
你的算法的时间复杂度应该在O(log n)之内
如果数组中不存在目标，返回[-1, -1].
例如：
给出的数组是[5, 7, 7, 8, 8, 10]，目标值是8,
返回[3, 4].
思路一：
先采取二分思路，查找到中间节点mid=target时，然后向两端拓展 找到left right边界
不足：最坏时间复杂度 O(N) 当数组全部为target元素时发生
思路二：
二分分别查找 left right两个端点
易错点： while循环为 left<=right 并且最终的边界 需要判断是否符合 即边界必须存在 且其值为target
vector<int> searchRange(int* A, int n, int target) {// write code herevector<int> res;int l1=0,r1=n-1;while(l1<=r1){int mid=(l1+r1)/2;if(A[mid]<target)l1=mid+1;elser1=mid-1;}//最终 l1是第一个targetif(l1>=0 && l1<n && A[l1]==target)res.push_back(l1);elseres.push_back(-1);int l2=0,r2=n-1;while(l2<=r2){int mid=(l2+r2)/2;if(A[mid]>target)r2=mid-1;elsel2=mid+1;}//最终 r2是最后一个targetif(r2>=0 && r2<n && A[r2]==target)res.push_back(r2);elseres.push_back(-1);return res;}