34 在排序数组中查找元素的第一个和最后一个位置
模板题
class Solution {
public:
// 找左边界
int left_bound(vector<int>& nums, int target){
int left = 0, right = nums.size();
while(left < right){
int mid = left + (right - left) / 2;
if(target == nums[mid]){
right = mid;
}else if(target < nums[mid]){
right = mid;
}else if(target > nums[mid]){
left = mid + 1;
}
}
if(left < 0 || left >= nums.size())
return -1;
return nums[left] == target ? left : -1;
}
// 找右边界
int right_bound(vector<int>& nums, int target){
int left = 0, right = nums.size();
while(left < right){
int mid = left + (right - left) / 2;
if(target == nums[mid]){
left = mid + 1;
}else if(target < nums[mid]){
right = mid;
}else if(target > nums[mid]){
left = mid + 1;
}
}
if(left - 1 < 0 || left - 1 >= nums.size())
return -1;
return nums[left - 1] == target ? left - 1 : -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
int idx1 = left_bound(nums, target);
int idx2 = right_bound(nums, target);
return {idx1, idx2};
}
};