title: 0x04 二分
date: 2019-02-07 18:34:50
categories: 算法竞赛进阶指南
tags: 二分
mathjax: true

更好的阅读体验

整数域二分

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

版本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. Cosmos二分答案模板及二分答案问题讲解
2. yxc二分查找算法模板
3. 《算法竞赛进阶指南》 lyd