二分

注意事项

• 求第一出现位置 相当于lower_bound()
• 求最后一次出现的位置后面一个位置,相当于upper_bound()
• 二分只是枚举的一种方式
• for循环是每个都遍历
• 满足check()的答案只有一个，就不用分左边界，右边界了，或者说左边界就等于右边界 l=r=x
• 满足check()的答案是一个范围l,r，也就是要根据题目意思得到左边界或者右边界

区分左边界还是右边界，主要看check(m)满足的情况下移动r还是l
如果要得到左边界则r = m, 右边界就是 l = m;

标准二分

左边界

找左边界时，选择mid偏左，mid = (l + r) >> 1

int bsearch_1(int l, int r){
    while (l < r){
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}


注意这个mid分到了左边区间，因为我们是寻找左边界
[l,mid] [mid+1,r]
如果mid满足条件，就查找[l,mid]区间

右边界

找右边界时，选择mid偏右，mid = (l + r + 1) >> 1

int bsearch_2(int l, int r){
    while (l < r){
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
注意这个mid分到了右边区间，因为我们是寻找右边界
[l,mid-1] [mid,r]
如果mid满足条件，就查找[mid,r]区间

整数二分

bool check(int mid) {
    // 检查 mid 是否可行
}
int binary_search() {
    int l = 0, r = max_ans;  // 求最大值    右边界
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
             l = mid;
        } else {
             r = mid - 1;
        }
    }
    return l;
}
int binary_search() {
    int l = 0, r = max_ans;  // 求最小值    左边界
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
             r = mid;
        } else {
             l = mid + 1;
        }
    }
    return l;
}

数组二分

用check函数来找有序数组的值

// 在nums找到最左边的2和最右边的2

vector<int> nums{1,2,2,2,3};
int val = 2;

// 右边界
bool check(int mid) {
    // 检查 mid 是否可行
    return nums[mid] <= val;
}
int binary_search() {
    int l = 0, r = nums.size();  // 求最大值    右边界
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) {
             l = mid;
        } else {
             r = mid - 1;
        }
    }
    return l;
}

// 左边界
bool check(int mid) {
    // 检查 mid 是否可行
    return nums[mid] >= val;
}
int binary_search() {
    int l = 0, r = nums.size();  // 求最小值    左边界
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
             r = mid;
        } else {
             l = mid + 1;
        }
    }
    return l;
} 

// 无边界
vector<int> nums{1,2,2,2,3};
int val = 2;
int binary_search() {
    // nums 从小到大
    int l = 0, r = nums.size()-1, ans=-1;  // 求最大值    右边界
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] == val) {
            ans = mid;
            break;
        }if(nums[mid] < val){
            l = mid+1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}
 
 // 右边界
int bsearch(int a[], int l, int r, int v) {//查找区间是[x,y)  返回的位置却可能是 y
    while (l < r) {
        int m = (l + r + 1) >> 1;
        if(a[m] == v) l = m;
        else if(a[m] > v) r = m - 1;
        else l = m;
    }
    return l;
}
// 左边界
int bsearch(int a[], int l, int r, int v) {//查找区间是[x,y)  返回的位置却可能是 y
    while (l < r) {
        int m = (l + r) >> 1;
        if(a[m] == v) r = m;
        else if (a[m] > v) r = m;
        else l = m + 1;
    }
    return l;
}

浮点数二分

浮点数eps，这里保留两位小数，1e-2往后再保留两位就行，1e-4

double binary_search() {
    double l = 0, r = max_ans;  // 求最大值  右边界
    while(r - l > eps){ 
        double mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    return  l;
    //return r;
}
 
double binary_search() {
    double l = 0, r = max_ans;  // 求最大值  左边界
    while(r - l > eps){ 
        double mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    return  l;
    //return r;
}
 
因为r - l > eps 所以r l值几乎相等，返回哪个都一样