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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
问题描述：给定一个排序的整数数组，找到一个给定值的起始和终止位置，算法的时间复杂度是O(log n)。
由于算法的时间复杂度是O(log n)，因此，可以采用二分查找，只不过当查找到给定的值时，要向左和向右进行延伸，看是否有重复的元素。
class Solution {
public:
vector searchRange(int A[], int n, int target) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int left = 0, right = n - 1, mid = 0;
vector
vec;
while(left <= right) {
mid = (left + right) / 2;
if(target > A[mid])
left = mid + 1;
else if(target < A[mid])
right = mid - 1;
else {
int i = mid;
while(i >= left && A[i] == target)
--i;
int j = mid;
while(j <= right && A[j] == target)
++j;
vec.push_back(++i);
vec.push_back(--j);
return vec;
}
}
vec.push_back(-1);
vec.push_back(-1);
return vec;
}
};