..
二分
二分
前言
众所周知：
二分属于算法基础，是每位 OIer 不可或缺的基本功。
但在编码过程中往往会由于各种细节处理不到位而出错。
本文主要从 二分的本质 角度来研究这一问题。
引入
在学习二分时，通常使用的例题是：
给定长度为 $n$ 的单调不增的非负整数序列 $a$，求 $q$ 在 $a$ 中首次出现的位置。
根据学习结果，可以得出一个结论：
二分的前提是具有单调性。
“具有单调性” 有语病，缺少主语。
主语是什么我也不知道老师没教过。
即 值域 关于 定义域 单调。
例题中为：$a_i$ 关于 $i$ 单调。
我要说的是，单调性并不是二分的前提。
二分的前提
序列的划分
我们将序列 $a$ 分为两部分：
- $\forall i \in [1, mid), a_i < q$
- $\forall i \in [mid, n], a_i >= q$
- 序列 $a$ 被分为 $[1, mid)$ 和 $[mid, n]$ 两个区间；
- 左区间任意元素小于 $q$
- 有区间任意元素不小于 $q$
划分的依据
我们定义一个性质 $Q$：
- 若实数 $a_x < q$，则称 $x$ 不具有性质 $Q$；
- 若实数 $a_x >= q$，则称 $x$ 具有性质 $Q$。
上述划分的依据是：序列元素是否具有性质 $Q$。
因此，二分的前提是：
序列能否根据某种性质划分为前后两部分。
二分的本质
序列划分后，我们考虑如何求解问题。
我们将问题拆成两部分：
- 查找第一个不小于 $q$ 的元素位置 $x$；
- 判断 $a_x$ 是否等于 $q$。
考虑问题 $1$ 如何求解。
不难发现，问题 $1$ 的答案 $i$，就是序列划分中的 $mid$。
故问题转化为：求右区间的左端点。
因此，二分的本质是：
求序列划分的区间交界点。
二分的写法
编写一个 $check$ 函数来判断元素是否具有某种性质。
- 规定左区间为不符合该性质；
- 规定有区间为符合该性质。
求左区间的右端点
int BinarySearch() {
int l = 1;
int r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) r = mid - 1;
else l = mid;
}
return l;
}
求右区间的左端点
int BinarySearch() {
int l = 1;
int r = n;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
这里解释一下为什么 mid = (l + r + 1) / 2。
假如刚好 $r = l + 1$，则 $mid = (l + r) / 2 = l$。
若 $check(mid)$ 为假，$mid$ 将被更新为 $l$，其值未发生变化，导致死循环而 $\text{TLE}$。
标程
#include <cstdio>
const int maxN = 1e6;
int n, m;
int a[maxN + 10];
int q;
bool check(int x) {
if (a[x] >= q) return true;
return false;
}
int BinarySearch() {
int l = 1;
int r = n;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
scanf("%d", &q);
int pos = BinarySearch();
if (a[pos] == q) printf("%d ", pos);
else printf("%d ", -1);
}
return 0;
}