Title
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 = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Solution
//cpp:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int a1=-1, a2=-1;
int lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (nums[m] == target) {
a1 = m;
hi--;
}
else if (nums[m] < target) {
lo = m + 1;
}
else {
hi = m - 1;
}
}
cout << lo << " " << hi << endl;
lo = 0, hi = nums.size() - 1;
while (lo <= hi) {
int m = lo + (hi - lo) / 2;
if (nums[m] == target) {
a2 = m;
lo++;
}
else if (nums[m] < target) {
lo = m + 1;
}
else {
hi = m - 1;
}
}
cout << lo << " " << hi << endl;
return { a1,a2 };
}
};