Appearance
简介
玩个游戏。
- 想一个
以内的正整数 ; - 每次我给出一个整数
,告诉我「 」「 」或「 」。
我能保证在
首先我猜
; 。
然后如法炮制,重复给出可行范围的中间数,每次都能把范围折半。由于
EXAMPLE
, ; , ; , ; , ; , ; , ; , ; , 。
条件
数组须呈现广义上的「单调性」。
将数组
原理
查找数组
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:为何循环的条件是
?我在其他参考书上看的是 。 A:在我的版本中,当
时, 或 就是要找的分割点,此时应退出循环。故循环能进行的条件是 。
Q:针对一段数组区间,比如对
进行二分查找怎么办? A:在程序开头令
,此举的目的是保证 能取到范围端点 或 。
Q:
会溢出 的范围吗? A:不会。那时已因不满足
而退出循环了。
Q:如果反过来,数组
的前段满足 ,后段不满足 怎么办? A:我们把两种情况都讨论一遍。
若前段
不满足 ,后段 满足 :
总不满足 , 总满足 。 - 因此当
满足 时,应令 ,否则令 。 - 第一个满足
的是 。 若前段
满足 ,后段 不满足 :
总满足 , 总不满足 。 - 因此当
满足 时,应令 ,否则令 。 - 最后一个满足
的是 。
整数域上的二分
在单调递增数组
前段
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];
}
在单调递增数组
前段
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];
}
实数域上的二分
实数域上的二分需要指定精度
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;
}