11-18 22:05 已编辑湖南工业大学嵌入式工程师发布于湖南

关注

二分&三分

二分

二分的定义

二分是一种利用“有序性”或“单调性”，通过每次将搜索区间缩小一半来快速定位目标值或最优解的位置的算法。

适用条件：

数据本身具有单调性或者有序性。

二分内check函数的判断结果成有序排列，例如：

false，false，...，false，true，true...

时间复杂度

二分算法单次的时间复杂度为 $log_2(n)$ ,假设一个数组的大小为 $2*10^5$ ,则单次查询的所需要计算的时间不超过 $20$ ,非常迅速。

而在一般的题目中，题面会给出一个 $n$ 大小的，一般 $n$ 的大小为 $10^5$ ~ $2*10^5$ .此时题目的总时间复杂度会是 $O(n*log_2(n))$ ,一般这个时间复杂度不会超过 $10^8$ (python除外)

二分模板

整形二分

整形二分要考虑区间边界问题，否则会死循环。以下有几个模板

[l, r]
int l = L, r = R;
while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
        r = mid - 1;   
    } else {
        l = mid + 1;  
    }
}

[l, r)
int l = L, r = R; 
while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
        r = mid;     
    } else {
        l = mid + 1; 
    }
}

(l, r)
int l = L, r = R; 
while (l + 1 != r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
        r = mid;     
    } else {
        l = mid; 
    }
}

浮点数二分

double l = L, r = R; 
while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid)) {
        r = mid;     
    } else {
        l = mid; 
    }
}

二分的种类

我们遇上的大部分二分题目简单可以分为两种：二分查找以及二分答案.

简单来说，

二分查找就是在一个有序数组序列中快速查找一个值，

二分答案就是在题目给出的范围中通过不断二分，来找到一个能满足题目条件的最优解。

1.二分查找

https://www.luogu.com.cn/problem/P2249

很显然，题目给出的是一个单调性序列。但是比赛中基本上不会出二分查找的题目的。 alt

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int binary(int x){
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(a[mid]>=x) r=mid-1;
		else l=mid+1;
	}
	if(a[l]==x) return l;
	else return -1;
}
int main(){
    ios::sync_with_stdio(false);
	cin>>n>>m;
	int search;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>search;
	    int ans=binary(search);
	    cout<<ans<<" "; 
	}
	return 0;
}

2.二分答案

什么是二分答案？答案属于一个区间，当这个区间很大时，很可能会超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会可以进行二分答案。每一次二分会做一次判断，看是否对应的那个量达到了需要的大小--即对应写的check()函数。

判断：根据题意写个check函数，如果满足check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

来一道经典题

例题：https://www.luogu.com.cn/problem/CF1873E alt

题目中要求我们用 $w$ 单位的水去求出我们能建造的最大的水箱高度，当然 $a_i$ 最大可以到达 $10^9$ ,所以答案可能会有 $[0,10^9+w]$ 的情况，如果此时我们尝试暴力的话，就可能会狠狠超时，所以我们换一个思路，设 $h$ 到 $x$ 高度他就不能满足 $sum_x<=w$ 了，也就是说在 $x$ 之前所消耗的水都是满足条件的，而大于 $x$ 所消耗的水的总和就不能填充预设所需要的单位水量。现在我们就要求出这个边界条件。

这个题目的区间里面的数显然是单调上升的，满足二分条件我们就可以考虑二分答案，对 $h$ 进行枚举，枚举左侧边界设计为 $l=0$ ,右侧边界设为 $r=10^9+w$ ,右边界可以尽量开大一点。

然后设计check函数。捣鼓两下就能写出来了。看代码

int v[N]; 
// check函数：判断能否将所有 v[i] 都提升到 mid 这个值（阈值）。
// mid: 尝试达到的目标值。
// 返回值：如果总花费不超过预算 m，则返回 true。
bool check(int mid) {
    // res: 累计需要的总花费（使用 long long 防止溢出）。
    long long res = 0; 
    // 遍历所有元素。
    for (int i = 1; i <= n; i++) {
        // 计算将 v[i] 提升到 mid 所需的花费。
        // 如果 v[i] 已经 >= mid，则花费为 0。
        res += max(0LL, mid - v[i]);
    }
    // 检查总花费是否在预算 m 之内。
    return res <= m; 
}
void solve() {
    cin >> n >> m; 
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    // 初始化二分查找区间 [l, r)。
    // l: 可能的最大答案（下界）。
    // r: 不可能的最大答案（上界 + 1）。1e12 是一个足够大的数。
    long long l = 0, r = 1e12;
    while (l + 1 < r) {
        long long mid = (l + r) / 2; 
        // 如果 mid 可行（花费 <= m）。
        if (check(mid)) {
            // 尝试更高的目标值，将 l 移动到 mid。
            l = mid; 
        } else {
            // 如果 mid 不可行（花费 > m）。
            // 必须降低目标值，将 r 移动到 mid。
            r = mid;
        }
    }
    // 循环结束后，l 即为在预算 m 内能达到的最高统一目标值。
    cout << l << endl; 
}

如何判断一个题是不是用二分答案做的呢?

1、答案在一个区间内（一般情况下，区间会很大，暴力超时）

2、直接搜索不好搜，但是容易判断一个答案可行不可行

3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。

此外，可能还会有一个典型的特征：求最大值的最小或者求最小值的最大，90%的标答就是二分。

来个例题：https://www.luogu.com.cn/problem/P2678

alt 这题我们一看如果要枚举移走 $M$ 块石头的方案的话，我们要枚举 $\sum_{i=0}^{M} \binom{i}{n}$ 次，但是 $N,M$ 都可能到达 $5*10^5$ ,包会超时的。我们不妨换个角度，他要我们求最短跳跃距离的最大值，我们可以枚举最短跳跃距离，从 $min(a[i+1]-a[i])$ 枚举到 $10^9$ ，这显然是单调递增的，我们可以使用二分答案进行枚举，假设当前枚举的最短跳跃距离为 $mid$ 的话，遍历一遍数组，我们从左往右跳，每次尽量落在满足距离 $≥ mid$ 的下一块石头，如果一块石头离上一次落脚点的距离 $< mid$ ，就必须移除它。如果遍历完毕后搬石头的次数大于规定次数，则更新左区间，否则更新右区间。

这样一来我们就分析清楚了，下面上代码：

int n, m;
int L;
ll a[500005];
ll ans;
// 检查当前最小跳跃距离 x 是否可行
bool check(int x){
    ll cnt = 0;   // 记录需要移除的石头数量
    ll pos = 0;   // 上一次成功落脚的石头位置（索引），初始为起点
    for(ll i = 1; i <= n + 1; i++){   // 遍历所有石头，包含终点 L（作为 a[n+1]）
        // 如果当前石头与上一次落脚点距离小于 x，则不够跳，必须移除
        if(a[i] - a[pos] < x) cnt++;
        else pos = i;  // 否则可以落在当前石头上，更新落脚点
    }
    // 如果移除数量超过允许的上限 m，则最小跳跃距离 x 不可行
    return cnt <= m;
}
void solve(){
    cin >> L >> n >> m;   // L = 终点位置，n = 石头数，m = 可移除石头数
    for(int i = 1; i <= n; i++) cin >> a[i];  // 读入石头位置
    a[n + 1] = L;  // 把终点当成最后一块石头处理
    ll lf = 0, rg = L;  // 二分最小跳跃距离范围 [0, L] 
    while(lf <= rg){
        ll mid = (lf + rg) >> 1;  // 枚举当前最小跳跃距离
        if(check(mid)){
            // mid 可行，尝试更大的最小跳跃距离
            ans = mid;
            lf = mid + 1;
        }
        else{
            // mid 不可行，缩小范围
            rg = mid - 1;
        }
    }
    cout << ans << endl;  // 输出最大化后的最小跳跃距离
}

一般二分考察的形式多样，有可能是单纯的二分答案，在二分里面夹带点思维，比如说贪心，也有可能是其他数据结构算法之类的题目，需要二分算法来进行优化。还是很权威的。

三分

三分算法其实是二分算法的衍生，也可以说三分是二分的进阶版，

三分算法一般是拿来求一个函数的单峰极值，这一点相较二分更简单。

三分法与二分法的最大区别，就是把求解区间一分为三,二分是一分为二。之后我们也可以通过同样的缩小区间的方式来解决问题。

只不过我们会在循环中设两个中值一个 ${mid}_{r}$ ,以及 ${mid}_{l}$ ,然后不断更新区间，直到符合 while语句条件的时候就可以得出极值了。

核心的区间缩小逻辑（以求最大值为例）：

假设函数 $f(x)$ 为凸函数（开口向下，存在唯一的最大值）：

比较 $f(mid_1)$ 和 $f(mid_2)$ ：

如果 $f(mid_1) < f(mid_2)$ ： 说明极值点在 $mid_1$ 的右侧，位于 $[mid_1, R]$ 区间内。我们舍弃 $[L, mid_1]$ ，更新 $L = mid_1$ 。
如果 $f(mid_1) \ge f(mid_2)$ ： 说明极值点在 $mid_2$ 的左侧，位于 $[L, mid_2]$ 区间内。我们舍弃 $[mid_2, R]$ ，更新 $R = mid_2$ 。