Find First and Last Position of Element in Sorted Array
Find First and Last Position of Element in Sorted Array
Solution: Binary Search
The key lies in how we locate the left and right endpoints.
vector<int> searchRange(vector<int>& nums, int target) {
int start=0;
int end=nums.size()-1;
vector<int> res(2, -1);
if (end<0) return res;
// Move end as much as possible for greater or equal cases, lazily move start
while(start < end) {
int mid=(start+end)>>1;
if (nums[mid]<target) start=mid+1;
else end=mid;
}
if (nums[start]!=target) return res;
else res[0]=start;
end=nums.size()-1;
while(start < end) {
// If both start and end positions equal target, move start right to end the loop
int mid=((start+end)>>1)+1;
if (nums[mid]>target) end=mid-1;
else start=mid;
}
res[1]=end;
return res;
}#binary-search