何为二分?
举个例子,你和你的智障好友两人在一起玩猜数字游戏,你的智障好友想一个$[1,100]$的数让你猜。
线性扫显然是从1猜到100,当然为了防止你的好友故意卡你想了个98之类的数,你也可以从100猜到1。这样一定能得到正确答案因为你一个也不漏地猜完了。
但是如果给你说个条件,比如他每次都会告诉你你的猜想比他的数大还是小,那么这时候你就可以二分了。
怎么二分呢?(假设他想的数是98)
- 你猜50,他告诉你猜小了
- 你猜75,他告诉你猜小了
- 你猜87,他告诉你猜小了
- 你猜93,他告诉你猜小了
- 你猜96,他告诉你猜小了
- 你猜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 | int l=minn,r=maxx; |
但是这样容易得到死循环程序,所以我们在mid条件里写+1即可。。。
1 | int l=minn,r=maxx; |
嗯,还是死循环怎么办?
额,改成-1,再调调吧,说不定check写错了呢?说不定是这题不满足连续性呢?
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
赏
使用支付宝打赏
使用微信打赏
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏