34. Find First and Last Position of Element in Sorted Array
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return {-1, -1};
auto startIt = lower_bound(begin(nums), end(nums), target);
if(startIt == end(nums) || *startIt != target) return {-1, -1};
auto endIt = prev(upper_bound(begin(nums), end(nums), target));
return {(int)distance(begin(nums), startIt), (int)distance(begin(nums), endIt)};
}
};
|
