二分

二分模板一共有两个，分别适用与不同的情况。二分的一般思路是这样的：假设目标值在闭区间[l, r]中，根据题目我们提炼出一种性质，使用这种性质我们写一个 check 函数，它能将区间二分，通过检测 $mid=\frac{l+r}{2}$ 的 check(mid) 值把区间长度缩小一半（即二分区间），当 $l==r$ 时，我们就找到了二分的临界点，也就是目标值。

注意：二分一定能找到一个值，但是这个值是否是问题答案，需要看它是否满足题目要求，如果不满足要求则说明题目答案不存在。

二分模板

当我们将区间 [l, r] 划分为 [l, mid] 和 [mid + 1, r] 时，更新操作是 r = mid 或者 l = mid + 1， 计算 mid 时不需要加 1

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

	return l;
}

当我们将区间 [l, r] 划分为 [l, mid - 1] 和 [mid, r] 时，更新操作是 l = mid 或者 r = mid - 1， 计算 mid 时因为需要避免死循环所以需要加 1

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

	return l;
}

二分查找

二分查找又称折半搜索，它是在一个有序数组中查找某一元素的算法。时间复杂度为 $O(\log n)$。

// arr 为升序数组且长度为 len
bool binary_search(int arr[], int len, int target) {
	int l = 0, r = len - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        // ? 的条件怎么填？ > 还是 `>=`
        if (arr[mid] ? target) r = mid;
        else l = mid + 1;
    }

    return arr[l] == target;
}

最大值最小化

在有序数组中二分搜索可以用来查找满足条件的最大（最小）的值。要求满足条件的最大值的最小可能情况（最大值最小化），需要满足三个条件：

1. 答案在一个固定区间内
2. 查找符合条件的值困难，而判断某个值是否符合条件容易
3. 可行解对于区间满足一定的单调性。若 $x$ 满足条件则 $x+1$ 或 $x-1$ 必然也符合该条件。

何为有序？数组中的左侧或右侧都满足某一条件，而另一侧都不满足该条件，也可以看作是一种有序。

举例：在有序区间中查询大于等于 $x$ 的最小的那个值

最小值最大化

与最小值最大化同理，略。

举例：在有序区间中查询小于等于 $x$ 的最大的那个值

STL 中的二分查找

1. lower_bound：查找首个不小于给定值的元素
2. upper_bound：查找首个大于给定值的元素

典型例题

YBT 1244 和为给定数

问题描述：给出 $n$ 整数，询问其中是否有一对数的和等于给定的数 $m$。若存在和为 $m$ 的数对，输出这两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数对，输出一行 No

分析：枚举每一个数 $a$ 二分查找 $m-a$ 是否存在。

洛谷 P1678 烦恼的高考志愿

问题描述：现有 $m$ 所学校，每所学校预计分数线是 $a_i$​。有 $n$ 位学生，估分分别为 $b_i$。根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

分析：枚举每个学生的估分 $x$，分别在各个学校中二分查找出 $\ge x$ 的最小值 $a$，和 $\le x$ 的最大值 $b$,然后取 $min(|x-a|,|x-b|)$，相加即可。

二分答案

有时候我们遇到题目时往往考虑枚举答案然后检验枚举的答案是否正确。若答案区间满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了二分答案

洛谷 P1873. 砍树

分析：设锯子高度为 $h$ 则 $h$ 越低收割到的木材就越多，而锯子越高则收割到的木材就越少，当 $h$ 等于某一高度时可以满足所需的木材长度，高于这个 $h$ 都无法满足，小于等于这个 $h$ 都可以满足，答案具有单调性，可以二分。

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

const int N = 1e6 + 10;
long long n, m, a[N];

bool check(int mid) {
	long long s = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] > mid) s += a[i] - mid;
	}

	return s >= m;
}

int main() {
	cin >> n >> m;

	long long mx = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
	}

	long long l = 0, r = mx;
	while (l < r) {
		long long mid = l + r + 1>> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;

	return 0;
}

洛谷 P2440. 木材加工

题目描述：木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。对于 $100\mathrm{\%}$ 的数据，有 $1\le n\le {10}^5$，$1\le k\le {10}^8$，$1\le L_i\le {10}^8(i\in [1,n])$。

分析：首先需要确定答案区间范围，之后二分枚举答案（长度 $l$），判断当前答案是否可以切割成 $k$ 端，调整左右区间直到找到满足条件的最大值。

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

const int N = 1e5 + 10;
int a[N], n, k;

bool check(int len) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += a[i] / len;
    }

    return s >= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];

	// 答案区间范围的确定，还有没有更准确的范围？
    int l = 0, r = 1e8;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;

    return 0;
}

洛谷 P3853. 路标设置

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

int n, m, k, a[100010];

bool check(int mid) {
    int cnt = 0;
    for (int i = 2; i <= m; i++) {
        cnt += (a[i] - a[i - 1] - 1) / mid;
    }

    return cnt <= k;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> a[i];

    int l = 1, r = n;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;

    return 0;
}

洛谷 P1824. 进击的奶牛

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

int n, m, a[100010];

bool check(int x) {
    int cnt = 0, last = -1e9;
    for (int i = 1; i <= n; i++) {
        if (a[i] - last >= x) {
            last = a[i];
            cnt++;
        }
    }

    return cnt >= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;

    return 0;
}

YBT 1243. 月度开销

分析：最大月度开销的最小开销，求最大值的最小值——二分答案

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

const int N = 100010;
int n, m, a[N];

bool check(int mid) {
	int c = 1, money = 0;
	for (int i = 0; i < n; i++) {
		if(money + a[i] > mid) {
			money = a[i];
			c++;
		} else {
			money += a[i];
		}
	}
    // 月份等于 m 时正好分成m个月份
    // 小于 m 时可以将某些月份中的天数拆开组成新月份，满足分成 m 个月份
	return c <= m;
}

int main() {
	cin >> n >> m;
	int mmax = 0, sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mmax = max(mmax, a[i]);
		sum += a[i];
	}

	int l = mmax, r = sum;
	while (l < r) {
		long long mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}

	cout << l << endl;

	return 0;
}

实数二分

以上我们讲的都是整数二分，整数二分是需要考虑边界问题的，而实数二分比较简单，只需要考虑所需精度 eps 即可，一般题目需要保留k位小数时，精度通常设置为 $eps={10}^{k+2}$。

double eps = 1e-8;
while (l + eps < r) {
	double mid = (l + r) / 2;
	if (check(mid)) r = mid; // 或者是 l = mid
	else l = mid;            // 或者是 r = mid
}

// for 循环也可以实现，一般固定循环 1000 次
for (int i = 0; i < 1000; i++) {
	double mid = (l + r) / 2;
	if (check(mid)) l = mid;
	else r = mid;
}

洛谷 P1577 切绳子

分析：实数域上的二分答案

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

const int N = 100010;
int a[N], n, m;

bool check(double len) {
	// 剪长度为 len 的绳字是否能到 m 根
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += a[i] / len; // 一根绳子能剪出多少长度为 m 的绳子
        if (res >= m) return true;
    }

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];

    double l = 0, r = 1e9;
    while (r - l > 1e-4) {
        double mid = l + (r - l) / 2; // 为什么这么写？
        if (check(mid)) l = mid; // 若能剪出 mid 长度的
        else r = mid;
    }
    printf("%.2f", l);

	return 0;
}

洛谷 P1024. 一元三次方程求解

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

double a, b, c, d, eps = 1e-4;

double f(double x) {
    return a * x * x * x + b * x * x + c * x + d;
}

int main() {
    cin >> a >> b >> c >> d;

    for (int i = -100; i <= 100; i++) {
        double l = i, r = i + 1; // 计算区间 [l, r) 之间的根
        if (fabs(f(l)) < eps) printf("%.2lf ", l);
        else if (fabs(f(r)) < eps) continue;
        else if (f(l) * f(r) < 0) {
            while (r - l > eps) {
                double mid = (l + r) / 2;
                if (f(mid) * f(r) > 0) r = mid;
                else l = mid;
            }
            printf("%.2lf ", l);
        }
    }

	return 0;
}

快速幂

快速幂模板

// 递归写法
long long qmi(int a, int b, int p) {
	if (b == 0) return 1;
	if (b == 1) return a;
	if (b % 2 == 0) {
		long long t = qmi(a, b / 2, p);
		return t * t % p;
	} else {
		long long t = qmi(a, b / 2, p);
		t = t * t % p;
		t = t * a % p;
		return t;
	}
}

// 非递归写法
int qmi(int  a, int  b, int  p) {
	long long ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % p;
		a = (long long)a * a % p;
		b >>= 1;
	}

	return ans % p; // 如不写这一行请考虑 5 0 1
}

洛谷 P1226. 快速幂

问题描述：给你三个整数 $a,b,p$，求 $a^{b}modp$。 $0\le a,b<2^{31}$，$a+b>0$，$2\le p<2^{31}$。

分析：快速幂模板题

习题

1. AcWing 104. 最佳牛围栏
2. 洛谷 P1102. A-B 数对
3. 洛谷 P2678. NOIP2015 跳石头
4. 洛谷 P8647. 分巧克力
5. 洛谷 B3881. 栓奶牛
6. 洛谷 B3629. 吃冰棍
7. 洛谷 P2415. 集合求和
8. AcWing 878. 快速幂求逆元