34.在排序数组中查找元素的第一个和最后一个位置

😂二分查找

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(!nums.size())
            return {-1, -1};
        int left = search_left(nums, target);
        int right = search_right(nums, target);
        if(left > right) 
            return {-1, -1};
        return {left, right}; 
    }
    int search_left(vector<int>& nums, int target) {
        int lo = 0, 
        hi = nums.size(), m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] < target) {
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        return lo;
    }
    int search_right(vector<int>& nums, int target) {
        int lo = 0, 
        hi = nums.size(), m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] <= target) {
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        return lo - 1;
    }
};

Accepted

88/88 cases passed (12 ms)

Your runtime beats 49.48 % of cpp submissions

Your memory usage beats 5.07 % of cpp submissions (10.5 MB)