给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
思路1：先用二分法找到其中某个target，再向前向后一位一位地找头和尾；
思路2：改进一下，在第二步找头和尾时也用二分法；
#include <iostream>
#include <vector>
using namespace std; vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans={-, -};
if(nums.size()==) return ans;
if(nums.size()==&&nums[]==target)
return {,};
if(nums.size()==&&nums[]!=target)
return ans;
int low=;
int high=nums.size()-;
int mid=;
while(low<=high)
{
mid=(low+high)/;
if(nums[mid]==target) break;
if(target<nums[mid]) high=mid-;
else low=mid+;
}
if(low>high) return ans; int begin=mid;
int end=mid; low=;
int m1=mid;
int m2;
while(low<=m1)
{
m2=(low+m1)/;
if(nums[m2]==target&&(m2-)>=&&nums[m2-]<target)
{
begin=m2;
break;
}
if(nums[m2]==target&&m2==)
{
begin=m2;
break;
}
if(nums[m2]<target&&(m2+)<=m1&&nums[m2+]==target)
{
begin=m2+;
break;
}
if(nums[m2]==target&&(m2-)>=&&nums[m2-]==target) m1=m2-;
if(nums[m2]<target&&(m2+)<nums.size()&&nums[m2+]<target) low=m2+;
} high=nums.size()-;
if((mid+)<nums.size()&&nums[mid+]==target)
{
m1=mid+;
}
else
return {begin,mid};
while(m1<=high)
{
m2=(m1+high)/;
if(nums[m2]==target&&(m2+)<nums.size()&&nums[m2+]>target)
{
end=m2;
break;
}
if(nums[m2]==target&&m2==nums.size()-)
{
end=m2;
break;
}
if(nums[m2]>target&&(m2-)>mid&&nums[m2-]==target)
{
end=m2-;
break;
}
if(nums[m2]==target&&(m2+)<nums.size()&&nums[m2+]==target) m1=m2+;
if(nums[m2]>target&&(m2-)>mid&&nums[m2-]>target) high=m2-;
}
return {begin,end};
} int main() {
vector<int> a={,,}; int target=;
vector<int> ans=searchRange(a,target);
std::cout << ans[]<<ans[]<< std::endl;
return ;
}
