Type：medium
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input:nums = [5,7,7,8,8,10], target = 8Output:[3,4]
Example 2:
Input:nums = [5,7,7,8,8,10], target = 6Output:[-1,-1]
给定一个有序数组，查找target值出现的第一个位置和最后一个位置。若没有返回[-1， -1]。
要求的时间复杂度为O(log n)，因此仍然使用二分法。判断中间值与target的关系，决定下一次的搜索范围。若target等于中间值，则读取mid左右的值，直至不等于target，记录当前位置进ret数组。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n-1;
vector<int> ret;
ret.push_back(-1);
ret.push_back(-1);
while(left <= right){
int mid = left + (right - left)/2;
if(nums[mid] == target){
int temp = mid;
while(temp >= 0 && nums[temp] == target){
ret[0] = temp;
temp--;
}
while(mid < n && nums[mid] == target){
ret[1] = mid;
mid++;
}
return ret;
}else if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}
}
return ret;
}
};
