枚举优化算法：二分

0、猜数字游戏🎲

代码实现1️⃣ 🇨🇳

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
int main(void)
{
    srand(time(0));
    int x = rand() % 100 + 1;
    int y = x + 1;
    int cnt = 0;
    while (x != y)
    {
        cnt++;
        cout << "Please input your number:";
        cin >> y;
        if (x < y) cout << ">" << endl;
        if (x > y) cout << "<" << endl;
        if (x == y) cout << "you win in " << cnt << " times!" << endl;
    }
}

1、二分算法

当枚举的对象是单调序列时，就可以通过二分算法进行优化，快速逼近到正确解的位置。

由于单调的特征，我们可以每次计算 $mid = (L+R) / 2$，每次根据 $mid$ 的判定结果，排除掉左区间 $[L, mid]$ 或右区间 $(mid, R]$。

例如－假设序列 $A$ 单调递增，查找值为 $k$：

如 $a[mid] > k$，则对于右区间所有下标 $i$，都有 $a[i] > k$，因此可以让 $R=mid-1$;

如 $a[mid] < k$，则对于左区间所有下标 $i$，都有 $a[i] < k$，因此可以让 $L=mid+1$。

2、常用场景

二分的前提是单调性，典型的场景比如：

• 查找答案
• 二分区间
• 函数求解
• 最优值
• 最小值最大化
• 最大值最小化

3、抽象模型

3.1 二分模型

状态空间分为左右两个子区间，$[L, mid]$ 和 $(mid, R]$

$check(mid)$ 用来判定 $mid$（维度）对应的状态是否满足右侧条件，为真则将 $R$ 往 $mid - 1$ 变，为假则将 $L$ 往 $mid + 1$ 变;

循环以上过程，直到 $L$ 和 $R$ 重合之后的下一次变化，让 $R$ 变到 $L$ 左边，$mid$ 的开闭情况根据试题而定，影响最终结果的取值（为 $L$或 $R$）。

while (L <= R) 
{
  int mid = (L + R) / 2;
  if (check(mid))
    R = mid - 1;
  else
    L = mid + 1;
}
cout<<L;//or R

3.2 check函数和解

$check(mid)$ 函数表示 $mid$ 对应的状态落在左侧还是右侧区间，用来指导 $L$ 或 $R$ 的变化。

在二分循环结束后，$L$ 在右区间的最左端，$R$ 在左区间的最右端，因此要根据试题来设计 $check$ 函数（实际就是设计左右区间的开闭），最后取 $L$ 或 $R$ 为解。

例如：

• 第一个大于等于：$mid>= k$ 表示右侧，$mid<k$ 表示左侧，解取 $L$（右区间的最左端）
• 第一个大于：$mid>k$ 表示右侧，$mid<=k$ 表示左侧，解取 $L$（右区间的最左端）
• 最后一个小于等于：$mid>k$ 表示右侧，$mid<=k$表示左侧，解取 $R$（左区间的最右端）
• 最后一个小于：$mid>=k$ 表示右侧，$mid<k$ 表示左侧，解取 $R$（左区间的最右端）

3.3 解题思路

一般根据试题提炼出题目，识别维度、状态、解，假如可以转化成对状态进行判定来求解的，就可以用枚举实现。

进一步，如果状态区间是单调的，就可以使用二分来逼近求解。

4、实数二分

4.1 二分模板

double eps = 1E-6;
double L = 0, R = 1000000;
while(L <= R)
 {
  double mid = (L + R) / 2;
  if(check(mid))
    R = mid - eps;//eps是一个很小的数
  else
    L = mid + eps;
}

4.3 指定循环次数

有时候如果不好控制精度，也可以直接控制循环次数。例如设定循环次数为t次，则最后循环结束后R-L的值会是L/2^t。

int t = 100;
while(t-- > 0) {
//....
}

5. 二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。二分答案的前提是答案所在的值域满足单调性。

例题与练习

二分查找例题
P591 查找给定的K
CCFPB06D10 找数
P699 查找位置

分析：

1、朴素思路

朴素算法自然是枚举了，由于题目是找第一个等于，所以从左到右枚举，找到第一个就break，然后输出，如果循环结束还找不到（正常结束的下标==n+1），就输出－1。

显然，复杂度为O(n)。

2、二分思路

由于序列为单调的（本题为单调不减），可以考虑用二分的方法快速逼近。

二分答案例题
P28 切割绳子

二分答案练习题
CCFPB06D11月度开销
CCFPB06E04奶牛音节
P596 [NOIP2015 提高组] 跳石头
P320 不太甜的糖果

实数二分练习
P593求平方根
P594求函数零点