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

题目

题解

1. 挨个查找法

• 时间复杂度$O(N)$
• 空间复杂度$O(1)$

就是挨个查找数组，找到的第一个就是开始位置，找到的最后一个就是结束位置。
这个比较好写，但是对于这道题会超时

2. 二分查找法

• 时间复杂度$O(logN)$
• 空间复杂度$O(1)$

利用二分查找的性质，可以缩短时间复杂度

class Solution {//二分查找
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = find1stNum(nums,target);//找起始位置
        //start超出范围或者没找到start
        if(start==nums.size() || nums[start]!=target) return {-1,-1};
        int end = find1stNum(nums,target+1)-1;//找结束位置
        return {start,end};
        }
        
        int find1stNum(vector<int>& nums, int target){
            //定义开头和结尾
            //注意这里right不能是nums.size()-1，因为寻找结束位置的时候是找到其下一个的位置
            int left=0,right=nums.size();
            //进行二分查找
            while(left<right){
                int mid = left+(right-left)/2;
                //注意这里判断要用小于，来找到第一个数
                if(nums[mid]<target) left = mid+1;
                else right = mid;
            }
            return left;
        }
};