LeetCode

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

nkul · 10月1日 · 2020年 · 16次已读

两次二分找左右端点!

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        if(nums.empty()) return {-1,-1};

        int l = 0 ,r =nums.size() - 1;
        //先找左端点!
        while(l < r){
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1; 
        }

        if(nums[r] != target){
            return {-1,-1};
        }

        //此时l == r,故L = l = r;
        int L = l;
        //再找右端点!
        l = 0 ,r =nums.size() - 1;
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1; 
        }
        return {L,l};

    }
};



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!