整数二分

模板一

bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
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;
}

模板二

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

二分本质

思考：二分不是从中间分，从中间分只是逼近二分分界点的手段。

check（）函数要求检验一个数是否符合第二个区间而不符合第一个区间。

整数二分为什么有两个模板

整数二分即把区间（有序一定可二分，无序可能二分）按照一个标准划分为两个不连续区间.并查找分界点。

模板一我们最终要找的边界是一个性质在右半区符合，在左半区不符合的性质。我们要找符合的右半区的左边界点。管中窥豹的判断check（mid）,如果mid符合条件Mid是在右半区符合性质的半区中。要找左边界点的范围则更新为r = mid（包含Mid）。如果mid不符合条件，我们要找符合性质的左端点则l = mid + 1（已经确定mid是不符合的就从mid+1开始算）

模板二我们最终找的边界是一个性质在右半区不符合，在左半区符合的性质。并找到符合性质的左半区的右边界点。对mid进行判断来获得结果：如果mid符合条件，则mid就在左半区，那么我们要找的右边界点就可以更新为（mid,r）l = mid。如果mid不满足条件，则mid必然在右半区间，而我们要找的符合要求的左半区间性质的右端点就是（l,mid-1）。r = mid - 1;模板二要防止死循环：当mid = l + r >> 1时，加入l = r - 1当判断mid满足性质在左半区会更新为l = mid;而mid = (r - 1 + r)/2 = r - 0.5 = r - 1 = l(向下取整)，则更新完仍然是l = r- 1没变化会死循环。

记忆口诀

男左女右，女士优先，mid取反。