梁越

二分查找模板,包括左边界右边界

0 人看过

一次记住所有情况

二分法最怕的就是边界的处理,一般见到的就是下面三种情况

假设数组是升序的

查找元素

int binary(vector<int> nums, int target){
    int n=nums.size();
    int l=0, r=n-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]==target) return mid;
        else if(nums[mid]>target) r=mid-1;
        else l=mid+1;
    }

    return -1;
}

寻找左边界情况,右边要往左边靠

int binary(vector<int> nums, int target){
    int n=nums.size();
    int l=0, r=n-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]<target) l=mid+1;;
        else r=mid-1;
    }

    if(l>=n || nums[l]!=target) return -1;

    return l;
}

寻找右边界情况,左边要往右边靠

int binary(vector<int> nums, int target){
    int n=nums.size();
    int l=0, r=n-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(nums[mid]>target) r=mid-1;;
        else l=mid+1;
    }

    if(r<0 || nums[r]!=target) return -1;

    return r;
}