二分

玩个游戏.

• 想一个 $1000$ 以内的正整数 $n$.
• 每次我给出一个整数 $x$，告诉我「$n>x$」「$n<x$」或「$n=x$」.

我能保证在 $10$ 次以内猜到它.

首先我猜 $x=500$. 除了正好猜中以外，我能把 $n$ 的范围缩小一半.

• $n>x\intro n\in[501,1000]$
• $n<x\intro n\in[1,499]$

然后如法炮制，重复给出可行范围的中间数，每次都能把范围折半. 由于 $\log_2{1000}<10$，最多 $10$ 次就能确定 $n$.

例

$n=324$：

1. $x=500$. $n<x\intro n\in[1,499]$.
2. $x=250$. $n>x\intro n\in[251,499]$.
3. $x=375$. $n<x\intro n\in[251,375]$.
4. $x=313$. $n>x\intro n\in[313,375]$.
5. $x=344$. $n<x\intro n\in[313,344]$.
6. $x=328$. $n<x\intro n\in[313,328]$.
7. $x=320$. $n>x\intro n\in[320,328]$.
8. $x=324$. $n=x$.

数组须呈现广义上的「单调性」.

将数组 $a$ 对半分，前段都不满足 $P$，后段都满足 $P$，则可用二分算法确定分割点，进而确定「第一个满足 $P$ 的元素」.

查找数组 $a$（长度 $n$）中第一个满足条件 $P$ 的元素：

bool check(int k) {
	/* 返回 a[k] 是否满足条件 P */
}

int binQuery() {
	int l = 0, r = n + 1;
	while (l + 1 < r) {
		int m = (l + r) / 2;
		if (check(a[m])) r = m;
		else l = m;
	}
	return a[r];
}

作者列出了大家在学习二分算法中的一些疑问和解答，供参考学习.

Q：为何循环的条件是 $l+1<r$？我在其他参考书上看的是 $l<r$.

A：在我的版本中，当 $l+1=r$ 时，$a[l]$ 或 $a[r]$ 就是要找的分割点，此时应退出循环. 故循环能进行的条件是 $l+1<r$.

Q：针对一段数组区间，比如对 $a[L\cdots R]$ 进行二分查找怎么办？

A：在程序开头令 $l=L-1,r=R+1$，此举的目的是保证 $m=\left\lfloor\dfrac{ l+r}{2}\right\rfloor$ 能取到范围端点 $L$ 或 $R$.

Q：$m$ 会溢出 $[L,R]$ 的范围吗？

A：不会. 那时已因不满足 $l+1<r$ 而退出循环了.

Q：如果反过来，数组 $a$ 的前段满足 $P$，后段不满足 $P$ 怎么办？

A：我们把两种情况都讨论一遍.

若前段（$a[1\cdots l]$）不满足 $P$，后段（$a[r\cdots n]$）满足 $P$：

• $a[l]$ 总不满足 $P$，$a[r]$ 总满足 $P$.
• 因此当 $a[m]$ 满足 $P$ 时，应令 $r=m$，否则令 $l=m$.
• 第一个满足 $P$ 的是 $a[r]$.

若前段（$a[1\cdots l]$）满足 $P$，后段（$a[r\cdots n]$）不满足 $P$：

• $a[l]$ 总满足 $P$，$a[r]$ 总不满足 $P$.
• 因此当 $a[m]$ 满足 $P$ 时，应令 $l=m$，否则令 $r=m$.
• 最后一个满足 $P$ 的是 $a[l]$.

在单调递增数组 $a$（长度 $n$）中查找第一个 $\ge x$ 的数：

前段 $<x$，后段 $\ge x$，因此 $a[m]\ge x$ 时应令 $r=m$，最终答案是 $a[r]$.

int binQuery(int x) {
    int l = 0, r = n + 1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (a[m] >= x) r = m;
        else l = m;
    }
    return a[r];
}

在单调递增数组 $a$（长度 $n$）中查找最后一个 $\le x$ 的数：

前段 $\le x$，后段 $> x$，因此 $a[m]\le x$ 时应令 $l=m$，最终答案是 $a[l]$.

int binQuery(int x) {
    int l = 0, r = n + 1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        if (a[m] <= x) l = m;
        else r = m;
    }
    return a[l];
}

实数域上的二分需要指定精度 $eps$，以 $l+eps<r$ 为循环条件.

while (l + eps < r) {
    double m = (l + r) / 2;
    if (check(m)) r = m;
    else l = m;
}

此外还可采用固定次数的二分. 此方法得到的答案精度通常更高.

for (int i = 0; i < 1000; i ++) {
    double m = (l + r) / 2;
    if (check(m)) r = m;
    else l = m;
}