y总模板

y总的代码模板分为了两种情况：

• 【右真型】

  将区间[l, r]划分成[l, mid]和[mid + 1, r]：

  （适用于 000000000 2 111111111 类问题，即求可能的最小值问题）

    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;
    }

• 【左真型】

  将区间[l, r]划分成[l, mid - 1]和[mid, r]：

  （适用于 111111111 2 000000000 类问题，即求可能的最大值问题）

    int bsearch_2(int l, int r)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1; // 注意这里要 + 1 ！
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

顾名思义，根据真值集中在哪一侧而选择使用哪种模板。

【注】：0、1、2分别代表false、ture、target 。

$向下取整$：l + r >> 1 等价于 mid = (l + r) / 2 或 mid = l + (r - l) / 2

$向上取整$：l + r + 1 >> 1 等价于 mid = (l + r + 1) / 2 或 mid = l + (r - l + 1) / 2

【注】：在处理对象为整数时常用位运算，当l + r很大时（可能会爆），根据模板类型用 mid = l + (r - l) / 2 或 mid = l + (r - l + 1) / 2 。