本文章原出处：chicago01.top，转载不需说明，随意转载

整数域二分

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

[HTML_REMOVED]

版本1

当区间[l, r]的更新操作是r = mid; l = mid + 1;时，计算mid时不需要加1。

C++ 代码模板：

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

解读

我们要在下面一串数中用上面的二分查找代码查找 $11$

第一次查询，$(l + r)/2 = 4$，查到 $8$ ，是小于 $11$ 的，于是更新，$l = 4 + 1 = 5$

第二次查询，$(l + r)/2 = 6$ ，查到$12$ ，是大于$11$的，于是更新，$r = mid = 6$

第三次查询，$(l+r)/2 = 5$ ，查到$10$，是小于$11$的，于是更新，$l = 5+1 = 6$

最终得到结果为$12$ 。12是我们查找到这一串数中，大于等于11(查找数)中最小值。

我们可以得到一个结论：以上二分模板用来解，最大值最小问题。

版本2

当区间[l, r]的更新操作是r = mid - 1; l = mid;时，计算mid时需要加1。

C++ 代码模板：

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

解读

我们要在下面一串数中用上面的二分查找代码查找 $11$

第一次查询，$(l + r+1)/2 = 4$，查到 $8$ ，是小于 $11$ 的，于是更新，$l = 4$

第二次查询，$(l + r+1)/2 = 6$，查到 $12$ ，是大于 $11$ 的，于是更新，$r = 6-1 = 5$

第三次查询，$(l + r+1)/2 = 5$，查到 $10$ ，是小于 $11$ 的，于是更新，$l = 5$

最终得到结果为$10$ 。10是我们查找到这一串数中，小于等于11(查找数)中最大值。

我们可以得到一个结论：以上二分模板用来解，最小值最大问题。

二分答案

二分答案与二分查找类似，即对有着单调性的答案进行二分，大多数情况下用于求解满足某种条件下的最大（小）值。

答案单调性

答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：

1. 移动石头的个数越多，答案越大（NOIP2015跳石头）。

2. 前i天的条件一定比前 i + 1 天条件更容易（NOIP2012借教室）。

3. 满足更少分配要求比满足更多的要求更容易（NOIP2010关押罪犯）。

4. 满足更大最大值比满足更小最大值的要求更容易（NOIP2015运输计划）。

5. 时间越长，越容易满足条件（NOIP2012疫情控制）。

可以解决的问题

把求最优解的问题，转化为给定一个值 $mid$ ，判定是否存在一个方案，达到 $mid$ 的的问题。(二分答案转化为判定)。

1. 求最大的最小值（NOIP2015跳石头）。
2. 求最小的最大值（NOIP2010关押罪犯）。
3. 求满足条件下的最小（大）值。
4. 求最靠近一个值的值。
5. 求最小的能满足条件的代价。

一个小例子

有 $N$ 本书排成一行，已知第 $i$ 本书的厚度是 $A_i$ 。

把他们分成连续的 $M$ 组，$T$ 表示厚度之和最大的一组的厚度，使 $T$ 最小。

问的是最大值最小，很明显是一道二分题，题目让求 $T$ 值，我们可以直接来二分查找 $T$ 的值，在整数数轴上，肯定存在值，使得 $T$ 成立。呢么对应着使 $T$ 成立的这段数轴上，肯定也存在一个值，使得 $T$ 最小。

因此，可得，本题的做法就是，在整数数轴上二分查找一个 $T$ 值。

这道题也没有测试数据，只是书上的一个举例，我就不打打码了。

例1

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式

第一行输入整数 $N$ 和 $F$ ，数据间用空格隔开。

接下来 $N$ 行，每行输出一个整数，第$i+1$行输出的整数代表，第$i$片区域内包含的牛的数目。

输出格式

输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。

数据范围

$1≤N≤100000$
$1≤F≤N$

输入样例：

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例：

6500

题解：

题意：给$N$个数，找一个平均值最大的，且长度大于等于$F$的子段。

题目问的是让我们找一个最大值，这种最大，最小的问题，无碍于两种做法，一种是单纯的枚举，另一种是二分查找，当然后面还有一些更高级的算法。这道题的数据范围，很明显是二分查找(其实$10^5$枚举也可以，但是这里并不是整数，是可以存在小数的)。

• 二分查找出来一个平均值$avg$来判定，能否成立一个子段大于等于$F$组且大于等于这个平均值$avg$。

int search()
{
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(find(mid)) l = mid;
        else r = mid;
    }

    return (int)(r * 1000); 
}

• 可以利用前缀和，$sum[i] = sum[i-1] + num[i] - avg$ ，如果这个前缀和中存在连续长度大于等于$F$且和大于等于$0$，就成立了。

bool find(double avg)
{
    for(int i = 1;i <= n;++i)
        sum[i] = sum[i-1] + num[i] - avg;

    double minn = 0;
    for(int i = f,j = 0;i <= n;++i,++j)
    {
        minn = min(minn,sum[j]);
        if(sum[i] - minn >= 0)
            return true;
    }

    return false;
}

• 关于这个式子怎么推出，😂，我还小，我表达不清楚，如果非要说说，呢，大概是经验告诉我这个式子要这么写。

上全部代码：

#include<bits/stdc++.h>
using namespace std;

const int MAX = 100010;
int num[MAX],n,f;
double l,r;
double sum[MAX];

void init()
{
    cin >> n >> f;

    for(int i = 1;i <= n;++i)
    {
        cin >> num[i];
        r = max(r,(double)num[i]);
    }
}

bool find(double avg)
{
    for(int i = 1;i <= n;++i)
        sum[i] = sum[i-1] + num[i] - avg;

    double minn = 0;
    for(int i = f,j = 0;i <= n;++i,++j)
    {
        minn = min(minn,sum[j]);
        if(sum[i] - minn >= 0)
            return true;
    }

    return false;
}

int search()
{
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(find(mid)) l = mid;
        else r = mid;
    }

    return (int)(r * 1000); 
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);

    init();

    cout << search();

    return 0;
}

参考资料

1. Cosmos二分答案模板及二分答案问题讲解
2. yxc二分查找算法模板
3. 《算法竞赛进阶指南》 lyd
4. 秦淮岸~灯火阑珊 最佳的牛栏题解