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

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

题目

如果没有重复元素，我们可以用一遍二分就可以解决了。这道题有重复的元素

具体图示：

代码如下:

class Solution {
public:
    vector<int> searchRange(vector<int>& 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[l] != target) return {-1,-1};  
        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,r};
    }
};

时间复杂度:O(logn)
空间复杂度:O(1)