Skip to content

二分

2021-01-11

只有 10% 的程序员能写对二分。

简介

玩个游戏。

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

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

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

  • n>xn[501,1000]
  • n<xn[1,499]

然后如法炮制,重复给出可行范围的中间数,每次都能把范围折半。由于 log21000<10,最多 10 次就能确定 n

EXAMPLE

n=324

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

条件

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

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

原理

查找数组 a(长度 n)中第一个满足条件 P 的元素:

cpp
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[LR] 进行二分查找怎么办?

A:在程序开头令 l=L1,r=R+1,此举的目的是保证 m=l+r2 能取到范围端点 LR

Qm 会溢出 [L,R] 的范围吗?

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

Q:如果反过来,数组 a 的前段满足 P,后段不满足 P 怎么办?

A:我们把两种情况都讨论一遍。

若前段 a[1l] 不满足 P,后段 a[rn] 满足 P

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

若前段 a[1l] 满足 P,后段 a[rn] 不满足 P

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

整数域上的二分

在单调递增数组 a(长度 n)中查找第一个 x 的数:

前段 <x,后段 x,因此 a[m]x 时应令 r=m,最终答案是 a[r]

cpp
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)中查找最后一个 x 的数:

前段 x,后段 >x,因此 a[m]x 时应令 l=m,最终答案是 a[l]

cpp
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 为循环条件。

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

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

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