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

思路

题目要求时间复杂度为$O(logN)O(logN)$，并且本题是一个非递减的数组，所以我们可以使用二分法进行查找；

解题方法

1.解决方法1：暴力解法，时间复杂度：$O(N)O(N)$,空间复杂度为 $O(1)O(1)$； 2.解决方法2：二分法查找，时间复杂度：$O(logN)O(logN)$,空间复杂度为 $O(1)O(1)$；

Code：暴力解法

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size();
        int l=0,r=n-1;
        while(l<=r)//一次遍历
        {
            if(nums[l]==target&&nums[r]==target)
            {
                return vector<int>{l,r};
            }
            if(nums[l]!=target)//从前往后遍历
            {
                ++l;
            }

            if(nums[r]!=target)//从后往前遍历
            {
                --r;
            }

        }
        return vector<int>{-1,-1};//失败返回
    }
};

Code：二分法查找

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size();
        int leftIndex=searchIndex(nums,target,true);
        int rightIndex=searchIndex(nums,target,false)-1;
        if(rightIndex<n&&leftIndex<=rightIndex&&nums[leftIndex]==target&&nums[rightIndex]==target)//判断是否满足条件
        {
            return vector<int>{leftIndex,rightIndex};
        }
        return vector<int>{-1,-1};
    }
    int searchIndex(vector<int>& nums, int target,bool flag)
    {
        int l=0,r=nums.size()-1,ans=nums.size();
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(nums[mid]>target||(nums[mid]>=target)&&flag)//bool类型判断查找到的数字
            {
                ans=mid;
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        return ans;
    }
};