二分基础概念

二分 的基础用法是在 单调序列 或 单调函数 中进行查找。

因此当问题的答案具有 单调性 时，就可以通过 二分把求解化为判定。

有时在一些签到题上卡住的时候，不妨去想一想“二分”，这个简单的思想往往是最容易忽视的。

进一步地，还可以扩展到通过 三分 去解决 单峰函数 的 极值 以及相关问题。

不过大多情况下，在我们无法确定函数是 单峰 还是 多峰 时，优先推荐用 爬山法 来找极值

二分模板

整数域上二分

在单调递增序列

中查找

的数中最小的一个（即

或

的后继）：

while (l < r)
{
    int mid = (l + r) >> 1;
    if (a[mid] >= x) r = mid; else l = mid + 1;
}
return a[l];

在单调递增序列

中查找

的数中最大的一个（即

或

的前驱）：

while (l < r)
{
    int mid = (l + r + 1) >> 1;
    if (a[mid] <= x) l = mid; else r = mid - 1;
}
return a[l];

  C++ STL 中的 lower_bound 与 upper_bound 函数实现了在一个序列中二分查找某个整数

的后继，具体会在后面章节提及

实数域上二分

实数域上二分较为简单，确定好所需的精度

，一般需要保留

位小数时，取

while (l + eps < r)
{
    double mid = (l + r) / 2;
    if (calc(mid)) r = mid; else l = mid;
}

有时精度不容易确定或表示时，可以用迭代固定次数的二分方法，通常情况下精度会比预设更高

for (int i = 0; i < 100; i ++ )
{
    double mid = (l + r) / 2;
    if (calc(mid)) r = mid; else l = mid;
}

三分求单峰函数极值

有一类函数被称为 单峰函数（二次函数是特殊的单峰函数），它们有 唯一的极值点，且

1. （极大值点）在极值点左侧 严格单调上升，右侧 严格单调下降
2. （极小值点）在极值点左侧 严格单调下降，右侧 严格单调上升

以极大值点的单峰函数

为例，在函数定义域

上任取两个点

和

把函数分成三段

1. 若

，则有两种情况

与

同时处于极大值点左侧

处于极大值点左侧，

处于极大值点右侧

但是无论是哪种情况，极大值点都在

右侧，令

1. 若

，则有两种情况

与

同时处于极大值点右侧

处于极大值点左侧，

处于极大值点右侧

但是无论是哪种情况，极大值点都在

左侧，令

1. 若

，任意令

或

其中之一即可

如果取

和

为三等分点，那么定义域范围每次缩小

如果取

和

为二等分点两侧及其接近的地方，那么定义域范围每次近似缩小

无论哪种，都可在

级别的时间复杂度内求出指定精度的极值

  函数极值点左右两侧要求必须是严格单调的，否则在取等时，无法判断极值点的位置，就只能用爬山法了

整数域上三分

有唯一极大值点的单峰函数（严格凸函数）

while (l < r)
{
    int lmid = l + (r - l) / 3;
    int rmid = r - (r - l) / 3;
    if (calc(lmid) >= calc(rmid)) r = rmid - 1; else l = lmid + 1;
}
return max(calc(l), calc(r));

有唯一极小值点的单峰函数（严格凹函数）

while (l < r)
{
    int lmid = l + (r - l) / 3;
    int rmid = r - (r - l) / 3;
    if (calc(lmid) <= calc(rmid)) r = rmid - 1; else l = lmid + 1;
}
return min(calc(l), calc(r));

实数域上三分

while (l + eps < r)
{
    double lmid = l + (r - l) / 3;
    double rmid = r - (r - l) / 3;
    if (calc(lmid) >= calc(rmid)) r = rmid; else l = lmid;
}

二分答案转化为判定

  一个宏观的最优化问题可以抽象为函数，其“定义域”是该问题下的可行方案，对这些可行方案进行评估得到的数值构成函数的“值域”，最优解就是评估值最优的方案（不妨设评分越高越优）。

  假设最优解的评分为

，显然对于

，都不存在一个合法的方案达到

分，否则与

的最优性矛盾；而对于

，一定存在一个合法的方案达到或超过

分，因为最优解就满足这个条件。

  这样问题的值域就具有一种特殊的单调性 —— 在

的一侧合法、在

的另一侧不合法，就像一个在

上值为

，在

上值为

的分段函数，可通过二分找到这个分界点

。

  通过二分，我们把求最优解问题，转化为给定一个值

，判定是否存在一个可行方案评分达到

的问题。

例题

分书问题

题目描述

有

本书排成一行，已知第

本的厚度是

把它们分成连续的

组，使

最小化，其中

表示厚度之和最大的一组的厚度

输入格式

第一行输入两个整数

，数据用空格隔开

接下来

行，每行输出一个正整数

，表示第

本书的厚度

输出格式

输出最小整数

，其中

表示厚度之和最大的一组的厚度

数据范围

,

输入样例：

3 2
1 2 3

输出样例：

3

解析

“最大值最小” ，这是答案具有单调性，可用二分转化为判定的最常见、最典型的特征之一

如果我们以 “把书划分为

组的方案” 作为定义域，“厚度之和最大的一组的厚度” 作为评分（值域）

需要最小化这个厚度，也就是评分越小越优

假设最终答案为

，因为

的最优性：

1. 如果要求每组厚度都

，那么这

组一定不能容纳这些书，否则违背了

的最优性

1. 如果要求每组厚度都

，那么一定存在一种分书方案使得组数不会超过

最优解就处于分书可行性的分界点上，利用二分转化为判定进行求解即可

// 判定 n 本书分成 m 组，每组厚度之和 <= size，是否可行
bool valid(int size)
{
    int group = 1, rest = size;
    for (int i = 0; i < n; i ++ )
    {
        if (a[i] > size) return false;
        if (rest >= a[i]) rest -= a[i];
        else group ++ , rest = size - a[i];
    }
    return group <= m;
}
int main()
{
    //二分答案转化为判定
    int l = 0, r = accumulate(a, a + n, 0);
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (valid(mid)) r = mid; else l = mid + 1;
    }
    cout << r << endl;
    return 0;
}

最佳牛围栏

题目描述

农夫约翰的农场由

块田地组成，每块地里都有一定数量的牛，其数量不会少于

头，也不会超过

头。

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

围起区域内至少需要包含

块地，其中

会在输入中给出。

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

输入格式

第一行输入整数

和

，数据间用空格隔开。

接下来

行，每行输入一个整数，第

行输入的整数代表第

片区域内包含的牛的数目。

输出格式

输出一个整数，表示平均值的最大值乘以

再 向下取整 之后得到的结果。

数据范围

,

输入样例：

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

输出样例：

6500

解析

题目转译：给定正整数序列

，求一个平均数最大的，长度不小于

的子段

二分答案，判定“是否存在一个长度不小于

的子段，平均数不小于二分的值”

再把数列中每个数减去二分值，问题就转化为判定“是否存在一个长度不小于

的子段，子段和非负”

考虑一个子问题如何求解：求一个数列的最大子段和

最大子段和是一个经典模型，可以在线性的时间内完成求解，方法是不断把新的数加入当前子段，如果当前子段和变成了负数，就清空整个子段。扫描过程中出现的最大子段和即位所求。这里用到了动态规划的思想。

那么如何求一个长度不小于

的最大子段和呢？

将子段和转化为前缀和相减的形式，有：

这与上面直接求最大子段和有着异曲同工之妙，最大子段和维护的是

如果直接用前缀和来做，最大子段和维护的就是

前缀最小值

带长度不小于

限制的最大子段和维护的就是

前缀最小值

于是可以写出判定函数 valid 了：

bool valid(double avg)
{
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i] - avg;
    double min_val = 0;
    for (int i = m; i <= n; i ++ )
    {
        min_val = min(min_val, s[i - m]);
        if (s[i] > min_val) return true;
    }
    return false;
}

特殊排序

题目描述

有

个元素，编号

，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。

注意：不存在两个元素大小相等的情况。

也就是说，元素的大小关系是

个点与

条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过

次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这

个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的

函数

来获得两个元素之间的大小关系。

例如，编号为

和

的两个元素，如果元素

小于元素

，则 compare(a,b) 返回 true，否则返回 false。

将

个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围

输入样例

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例

[3, 1, 2]

解析

这里用二分法可能有点难以理解，不过给出数学证明就容易理解多了

由于题目中说明，元素之间的关系不具有传递性，因此会让我们觉得失去了单调的性质，就不能二分

不过还是可以证明二分的做法是正确的，假设前

个元素已经有序排好，现插入第

个元素：

情况一：第

个元素 < 第

个元素

则第

个元素一定能在区间

之间找到插入位置，用数学归纳法证明：

若第

个元素 大于 第

个元素，则第

个元素可以插在第

个元素 后面

若第

个元素 大于 第

个元素，则第

个元素可以插在第

个元素 后面

......

若第

个元素 大于 第

个元素，则第

个元素可以插在第

个元素 后面

若第

个元素 小于 第

个元素，则第

个元素可以插在第

个元素 前面

情况二：第

个元素 > 第

个元素

则第

个元素一定能在区间

之间找到插入位置，用数学归纳法同理易证

这样每次将查找区间缩小一倍，根据基于比较的排序的下界，可以在

的时间内完成排序

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        for (int i = 1; i <= N; i ++ )
        {
            int l = 0, r = res.size();
            while (l < r)
            {
                int mid = (l + r) >> 1;
                if (compare(i, res[mid])) r = mid; else l = mid + 1;
            }
            res.push_back(i);
            for (int j = res.size() - 1; j > l; j -- ) swap(res[j - 1], res[j]);
        }
        return res;
    }
};