Peter_Matthew的博客

二分

2019-01-09

何为二分?

举个例子,你和你的智障好友两人在一起玩猜数字游戏,你的智障好友想一个$[1,100]$的数让你猜。

线性扫显然是从1猜到100,当然为了防止你的好友故意卡你想了个98之类的数,你也可以从100猜到1。这样一定能得到正确答案因为你一个也不漏地猜完了。

但是如果给你说个条件,比如他每次都会告诉你你的猜想比他的数大还是小,那么这时候你就可以二分了。

怎么二分呢?(假设他想的数是98)

  1. 你猜50,他告诉你猜小了
  2. 你猜75,他告诉你猜小了
  3. 你猜87,他告诉你猜小了
  4. 你猜93,他告诉你猜小了
  5. 你猜96,他告诉你猜小了
  6. 你猜98,他告诉你猜对了

仔细分析对比两种方法,发现线性扫的每一步只会将答案存在区间缩小1($[1,100]->[2,100]->[3,100]->[4,100]->…[97,100]-> 98$然后找到答案,如果运继续搜是$[98,98]$),而二分的每一步都将答案区间缩小一半($[1,100]->(50,100]->(75,100]->(87,100]->(93,100]->(96,100]-> 98$,如果继续搜是$[98,100]->[98,99)->[98,98]$)

当然从时间复杂度角度来说,二分是$O(\log{n})$而线性扫是$O(n)$的,在n增大过程中显然也是二分快

二分条件

关于写法

额,我一般总是写死循环然后改,所以我先写成这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int l=minn,r=maxx;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}//得到成立的最大值

int l=minn,r=maxx;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}//得到成立的最小值

但是这样容易得到死循环程序,所以我们在mid条件里写+1即可。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int l=minn,r=maxx;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}//得到成立的最大值

int l=minn,r=maxx;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}//得到成立的最小值

嗯,还是死循环怎么办?
额,改成-1,再调调吧,说不定check写错了呢?说不定是这题不满足连续性呢?


知识共享许可协议

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

标签: 蒜法
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章