简介

玩个游戏。

• 想一个 $1000$ 以内的正整数 $n$；
• 每次我给出一个整数 $x$，告诉我「$n>x$」「$n<x$」或「$n=\phantom{0}$$\phantom{0}x$」。

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

首先我猜 $x=\phantom{0}$$\phantom{0}500$。除了正好猜中以外，我能把 $n$ 的范围缩小一半。

• $n>x\Rightarrow n\in [501,\phantom{0}$$\phantom{0}1000]$；
• $n<x\Rightarrow n\in [1,\phantom{0}$$\phantom{0}499]$。

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

EXAMPLE

$n=\phantom{0}$$\phantom{0}324$：

1. $x=\phantom{0}$$\phantom{0}500$，$n<x\Rightarrow n\in [1,\phantom{0}$$\phantom{0}499]$；
2. $x=\phantom{0}$$\phantom{0}250$，$n>x\Rightarrow n\in [251,\phantom{0}$$\phantom{0}499]$；
3. $x=\phantom{0}$$\phantom{0}375$，$n<x\Rightarrow n\in [251,\phantom{0}$$\phantom{0}375]$；
4. $x=\phantom{0}$$\phantom{0}313$，$n>x\Rightarrow n\in [313,\phantom{0}$$\phantom{0}375]$；
5. $x=\phantom{0}$$\phantom{0}344$，$n<x\Rightarrow n\in [313,\phantom{0}$$\phantom{0}344]$；
6. $x=\phantom{0}$$\phantom{0}328$，$n<x\Rightarrow n\in [313,\phantom{0}$$\phantom{0}328]$；
7. $x=\phantom{0}$$\phantom{0}320$，$n>x\Rightarrow n\in [320,\phantom{0}$$\phantom{0}328]$；
8. $x=\phantom{0}$$\phantom{0}324$，$n=\phantom{0}$$\phantom{0}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 & A

Q：为何循环的条件是 $l+\phantom{0}$$\phantom{0}1<r$？我在其他参考书上看的是 $l<r$。

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

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

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

Q：$m$ 会溢出 $[L,\phantom{0}$$\phantom{0}R]$ 的范围吗？

A：不会。那时已因不满足 $l+\phantom{0}$$\phantom{0}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=\phantom{0}$$\phantom{0}m$，否则令 $l=\phantom{0}$$\phantom{0}m$。
• 第一个满足 $P$ 的是 $a[r]$。

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

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

整数域上的二分

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

前段 $<x$，后段 $\ge x$，因此 $a[m]\ge x$ 时应令 $r=\phantom{0}$$\phantom{0}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=\phantom{0}$$\phantom{0}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];
}

实数域上的二分

实数域上的二分需要指定精度 $\mathrm{eps}$，以 $l+\phantom{0}$$\phantom{0}\mathrm{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;
}