二分算法模板

一、整数二分

二分的本质是查找边界，整数区间一分为二成两个区间，一部分满足性质1一部分满足性质2（如：左半边满足性质1，右半边满足性质2），那么既可以寻找性质1的边界，也可以寻找性质2的边界

每次将区间缩小一半，选择答案所在的区间

二分的本质不是单调性。有单调性的题目可以二分，但是可以二分的题目不一定有单调性

代码模板如下：

// 代码随想录写法，左闭右闭区间
int search(int left,int right){
    while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle] > target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else if (nums[middle] < target) {
            left = middle + 1; // target 在右区间，所以[middle + 1, right]
        } else { // nums[middle] == target
            return middle; // 数组中找到目标值，直接返回下标
        }
    }
}

题目示例：1，2，2，3，3，5找出3的起始位置和终止位置

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

二、浮点数二分

直接取mid判断落在哪个区间上，更新区间不断重复，直到精度足够为止(如：r - l < 1e-6)

bool check(double x){/* 检查x是否符合性质 */}

double bsearch(double l, double r){
    const double eps = 1e-6;
    while(r - l > eps){   // eps 表示精度，取决于题目对精度的要求
        double mid = (l + r) / 2; // 不断二分
        if(check(mid)){
            r = mid;
        }else{
            l = mid;
        }
    }
    return 1;
}