二分答案可以用于處理一系列涉及最大值最小值的問題，但是有一個嚴(yán)格的前提，就是答案需要擁有單調(diào)性。

這類型問題往往需要先求解出一個中間值，然后在求解答案，或是答案與某個不定的中間值有關(guān)。因此使用其他算法較難求解。

二分答案的基本代碼有很多種，存在細(xì)微差別

第一種是這樣的：

while (l<r) {mid=(l+r+1)>>1;if (check(mid)) r=mid;else l=mid+1; }

這里我們不單獨進(jìn)行答案的記錄，直接保存在l里面。

有幾個細(xì)節(jié)需要注意：

mid=(l+r+1)>>1

如果最后是2和3，那么mid=(l+r)>>1會卡死在2。

r=mid

這里是在求最小值的時候這么寫，最大值就是l=mid

如果寫r=mid-1或者l=mid+1就會把確認(rèn)正確的答案mid給排除，不可取。

第二種寫法是這樣的：

while (l<=r) {int mid=(l+r)/2;if (check(mid)) ans=mid，r=mid-1;else l=mid+1; }

這就是記錄答案版本的二分，由于我們每一次發(fā)現(xiàn)可行解的時候都把他記下來，所以收縮邊界的時候就不需要保留了。

二分的邊界問題是大部分錯誤的原因，在出現(xiàn)邊界問題的時候可以手造小數(shù)據(jù)，然后模擬程序跑幾遍。

當(dāng)然如果還是不行就最好重構(gòu)了

轉(zhuǎn)載于:https://www.cnblogs.com/ilverene/p/11135224.html

總結(jié)

以上是生活随笔為你收集整理的7.4 二分答案的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。