二分用到的挺多，三分用的少，但也不能忘。。。
二分我們常常用于一個具有單調(diào)性的情況中求解某值
而三分就像是求一個凸性或凹形函數(shù)時，來求那個凹凸點(diǎn)

一開始L=0，R=inf，然后也是不斷縮小L與R的范圍，逼近最值點(diǎn)

這里面有兩個中間點(diǎn)mid1與mid2
mid1=(L+R)>>1
mid2=(mid1+R)>>1
然后判斷mid1與mid2的大小關(guān)系，從而縮小不同范圍
當(dāng)while（L<R）不再滿足條件時，答案也就呼之欲出

詳細(xì)過程：

check()為三分的判斷函數(shù)
1.check(mid1)>check(mid2),我們可以得知最值點(diǎn)位于mid2的左側(cè)，我們通過R=mid2，將右邊界逼近來縮小范圍
因為如果mid1與mid2都在極點(diǎn)左側(cè)，check(mid1)就比check(mid2)小，不滿足條件。所以最值點(diǎn)只能在mid2左側(cè)

2.check（mid1）<check(mid2)，我們可以得知最值點(diǎn)一定位于mid1的右側(cè)，我們將左邊界縮小，L=mid1
為什么？如果最極點(diǎn)位于mid1的左側(cè)，mid1<mid2，mid2也在右側(cè)，那check的結(jié)果比較就與條件沖突

這講的是凸形狀，還有凹形狀，正好相反

代碼：

凸形狀
兩種寫法：

int three(int l,int r) //找凸點(diǎn) { while(l < r-1) { int mid1 = (l+r)/2; int mid2 = (mid1+r)/2; if( check(mid1) > check(mid2) ) r = mid2; else l = mid1; } return f(l)>f(r)? l : r; } double three(double l,double r) { double mid1,mid2; while(r-l>=eps) { mid1=l+(r-l)/3; mid2=r-(r-l)/3; if(f(m1)<=f(m2)) l=mid1; else r=mid2; } return (mid1+mid2)/2; }

這個題就可以用三分來做題目穿送

這里存一下二分的模板，沒地方放了

bool check(int mid){ …… return ……;} //模板一 找滿足某個條件的第一個數(shù) int binary1(int l, int r) {while(l<r){int mid=(r+l)>>1;if(check(mid) r=mid;else l=mid+1;}return l; } //模板二 找滿足某個條件的最后一個數(shù) int binary1(int l, int r) {while(l<r){int mid=(r+l+1)>>1;if(check(mid) l=mid;else r=mid-1;}return l; }

總結(jié)

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

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