何为二分？

举个例子，你和你的智障好友两人在一起玩猜数字游戏，你的智障好友想一个$[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 国际许可协议进行许可。