二分法

三、二分法

1.整数二分的本质：

将整个区间一分为二。在这两个区间，选择一个一定能保证里面有答案的区间，区间代码模板如下。

并且解决左右端点更新的问题

1. 程序中不要同时出现l = mid, r = mdi这两条语句。
2. 如过程序中出现了l = mid，mid的值用 (l + r + 1) / 2计算。
3. 如果程序中出现了r = mid，mid的值用（(l + r) / 2计算。

2.给出二分问题，怎么选择如下两个模板。(核心是看l=mid还是r=mid)

// 整数二分算法模板

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;
}
// 区间[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;
}

解题思路：（1）
一个mid = (l+r)>>1
一个mid = (l+r+1)>>1
加不加1 完全取决于 l = mid 还是r = mid
l等于mid时必须+1向上取整 不然会陷入l=l的死循环
r = mid 时候不用加1 因为下一步l = r 直接会退出循环
（2)
这两个模板解决的是 找>=||<=||>||< 某个数的
最左或最右的位置 但这个数不一定在二分的数组中
如果在就能准确找到
如果不在 找到的就是最接近答案的数（你要找大于等于5的第一个数）但
数组中没有5 那找到的就是6的位置(如果有6的话)
所以二分是一定有答案的。

3.浮点数二分

先确定边界，在判断在左边还是右边

代码模板

// 浮点数二分算法模板

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

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

4.例题

整数二分

输入 6 3 第二行1 2 2 3 3 4 第三行 3 第四行 4第五行 5 输出第一行3 4第二行5 5第三行-1 -1

#include <iostream>

using namespace std;

const int N = 100010;
int a[N];

int main()
{
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i ++) cin >> a[i];

    while (q --)
    {
        int k;
        cin >> k;
        int l = 0, r = n;    // 确定二分区间，这里 r 为 n(区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用)
        while (l < r)
        {
            int mid = l + r >> 1;// 是为了防止陷入死循环,如果 if(check(mid)) 后接的是 l = mid ，那么其前后必然是 int mid = l + r + 1 >> 1，else l = mid - 1。需要注意，最后出来的 l 和 r 必然是相等的。
            if (a[mid] >= k) r = mid;
             // a[mid] 大于等于 k 说明第一个大于等于 k 的元素一定在 mid 处或 mid 左边
            // 右边界变小，更加关注左半区间
            else l = mid + 1;
            //a[mid] 小于 k 说明第一个大于等于 k 的元素一定在 mid 右边(不包含 mid)
            // 左边界变大，更加关注右半区间
        }

        // 二分一定有答案，但要检查答案是否正确
        // 若序列中没有等于 k 的元素，查找出的是第一个大于 k 的元素的下标
        if (a[l] != k) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';
            int l = 0, r = n;
            while (l < r)
            {
                int mid = l + r >> 1;
                // 不同点在这里的 check 函数
                // 这一部分要寻找的是元素 k 的终止位置
                // 我们可以理解为求第一个满足大于 k 的位置，再将结果减 1 ，即是最后一个大于等于 k 的位置
                if (a[mid] > k) r = mid;
                else l = mid + 1;
            }
            // 这也是我们的 r 要开到 n 的原因，假设我们的目标 k 是 a[n-1]
            // 那么第一个大于 k 的下标将达到 n ，如果二分区间到不了这，将导致答案错误
            cout << l - 1 << endl;
        }
    }
    return 0;
}

浮点二分（区间的长度可以严格的缩小一半）

#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
    double x;
    cin >> x;
    double l=-10000,r=10000;
    const double eps = 1e-8;   // eps 表示精度，取决于题目对精度的要求
        while (r - l > eps)
        {
            double mid = (l + r) / 2;
            if (mid*mid*mid>=x) r = mid;
            else l = mid;
        }//最后l和r相差的会非常小
        printf("%lf\n",l);//l和r输出哪个都行
    return 0;
}