二分法模板

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

中间值计算

首先中间值计算要使用 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 则是最后一个，如果存在则判断前一个。