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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

logn级别的时间复杂度，可以直接想到二分法，分两次查找，第一次查找左边界，第二次查找右边界。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0) return {-1,-1};
        int l=0,r=nums.size()-1,m;
        int retl=-1,retr=-1;
        //find left
        while(l<r-1){
            m=(l+r)/2;
            if(nums[m]<target){
                l=m+1;
            }
            else if(nums[m]>target){
                r=m-1;
            }
            else if(nums[m-1]==nums[m]){
                r=m-1;
            }
            else{
                retl=m;
                break;
            }
        }
        if(retl==-1){
            if(nums[l]==target) retl=l;
            else if(nums[r]==target) retl=r;
            else return {-1,-1};
        }
        l=0,r=nums.size()-1;
        //find right
        while(l<r-1){
            m=(l+r)/2;
            if(nums[m]<target){
                l=m+1;
            }
            else if(nums[m]>target){
                r=m-1;
            }
            else if(nums[m+1]==nums[m]){
                l=m+1;
            }
            else{
                retr=m;
                break;
            }
        }
        if(retr==-1){
            if(nums[r]==target) retr=r;
            else if(nums[l]==target) retr=l;
        }
        
        return {retl,retr};
    }
};

附上一个更加高效的写法，别人的思维真的很精准。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int t) {
        if(nums.size()==0)return {-1,-1};
        vector<int> res;
        int l = 0, r = nums.size() - 1;

        //二分查找数组的性质 >=t 和 <=t
        //先二分左边边界 >=t
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= t)    r = mid;
            else l = mid + 1;
        }
        //判断是否有t 没有直接返回-1 -1
        if (nums[l] != t) return { -1,-1 };
        else {
            res.push_back(l);
            l = 0, r = nums.size() - 1;
            //右边边界 <=t 
            while (l < r) {
                int mid = l + r +1>> 1;
                if (nums[mid] <= t) l = mid;
                else r = mid - 1;
            }
        }
        res.push_back(l);
        return res;

    }
};

作者：ni-hen-you-xiu-2
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/c-er-fen-cha-zhao-ying-yong-by-ni-hen-you-xiu-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。