二分法模板

何言 2021年08月11日 60次浏览

对于一串有序线性表,要在里面查找某个值,想都不用想直接二分,但是实际问题不会简单的在线性表里查某个值,而是要求范围第一个大于某值的下标等,这种时候就涉及到一些边界的处理问题,这里整理出几个模板,以后遇到要用到二分的题可以直接套用模板。

中间值计算

首先中间值计算要使用 mid = left + (right-left)/2,如果直接使用 mid = (left+right)/2 ,会产生溢出问题。其次,如果除法操作改成右移一位的话效率会高一点。因此我的模板使用的是 mid = left + (right-left)>>1

基本模板:

查找第一个大于等于某个数的数的下标

/**
 * 查找第一个大于等于 target 的数的下标 否则返回 -1
 */
int findUpperEquals(vector<int> list, int target){
    int left = 0;
    int right = list.size()-1;
    int mid;
    while(left <= right>){
        mid = left + (right-left)>>1;
        if(list[mid] >= target){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return left < list.size() ? left : -1;
}

查找第一个大于某个数的数的下标

/**
 * 查找第一个大于 target 的数的下标 否则返回 -1
 */
int findUpper(vector<int> list, int target){
    int left = 0;
    int right = list.size()-1;
    int mid;
    while(left <= right>){
        mid = left + (right-left)>>1;
        if(list[mid] > target){
            right = mid-1;
        }else{
            left = mid+1;
        }
    }
    return left < list.size() ? left : -1;
}

以上就是基本模板了,使用这两个模板可以解决很多问题,例如:

寻找某数第一个出现的位置

思路就是寻找第一个大于等于该数的数,最后判断该数是不是目标数

/**
 * 查找 target 第一次出现的数的下标 否则返回 -1
 */
int findFirstNum(vector<int> list, int target){
    int r = findUpperEquals(list, target);
    return (r == -1 || list[r]!=target)? -1 : r;
}

寻找某数最后一个出现的位置

寻找第一个大于该数的数,在判断一下前一个是否为目标数

/**
 * 查找 target 最后一次出现的数的下标 否则返回 -1
 */
int findLastNum(vector<int> list, int target){
    int r = findUpper(list, target);
    return (r <= 0 || list[r-1]!=target)? -1 : r;
}

以下问题代码就不写出了,使用模板后就比较简单:

寻找某数出现的次数

寻找第一个和最后一个出现的位置后做差即可。

寻找小于某数的最大值

寻找第一个大于等于目标数的下标,如果为 -1 则是最后一个,如果存在则判断前一个。