跳转至

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};
    }
};