Given a sorted array of integers, 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].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res({-1, -1});
if (nums.empty()) {
return res;
}
int start = 0;
int end = nums.size() -1;
int idx = -1;
while (start <= end) {
int mid = (end + start) >> 1; // /2
if (nums[mid] == target) {
idx = mid;
break;
}
if (nums[mid] > target) {
end = mid -1;
}
else {
start = mid + 1;
}
}
if (idx == -1) {
return res;
}
for (end = idx; end < nums.size() -1; ++end) {
if (nums[end] != nums[end + 1]) {
break;
}
}
for (start = idx; start >0 ; --start) {
if (nums[start] != nums[start -1 ]) {
break;
}
}
res[0] = start;
res[1] = end;
return res;
}
};