博客

leetcode题目

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


本题要用二分查找来做

这篇题解启发很大


图解二分 | 最清晰易懂的讲解 | 一次性帮你解决二分边界问题【c++/java版本】

这篇题解指出，二分查找有两种边界问题需要解决，即num[mid]与target的大小关系（<=,>=,<,>），还有左右指针l和r的关系

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //[l,mid][mid+1,r]需要(l+r)/2;
        //而[l,mid-1][mid,r]需要(l+r+1)/2
        if(nums.size()==0) return {-1,-1};
        int l=0,r=nums.size()-1;
        //找左边界
        while(l<r){
            int mid=(l+r)/2;
            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){
            //为了避免向下取整导致 l==mid这种死循环出现
            int mid = (l+r+1)/2;
            //<=是因为要寻找target的右边界
            if(nums[mid]<=target) l=mid;
            else r=mid-1;
        }
        int R=r;
        return {L,r};

    }
};