二分

据说只有 10% 的程序员能写对二分.

简介 #

玩个游戏.

  • 想一个 $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 & A #

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

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;
}