算法 三分法

我們都知道 二分查找 适用于單調函數中逼近求解某點的值。

如果遇到凸性或凹形函數時，可以用三分查找求那個凸點或凹點。

下面的方法應該是三分查找的一個變形。

如圖所示，已知左右端點L、R，要求找到白點的位置。

思路：通過不斷縮小 [L,R] 的範圍，無限逼近白點。

做法：先取 [L,R] 的中點 mid，再取 [mid,R] 的中點 mmid，通過比較 f(mid) 與 f(mmid) 的大小來縮小範圍。

當最後 L=R-1 時，再比較下這兩個點的值，我們就找到了答案。

1、當 f(mid) > f(mmid) 的時候，我們可以斷定 mmid 一定在白點的右邊。

反證法：假設 mmid 在白點的左邊，則 mid 也一定在白點的左邊，又由 f(mid) > f(mmid) 可推出 mmid < mid，與已知沖突，故假設不成立。

是以，此時可以将 R = mmid 來縮小範圍。

2、當 f(mid) < f(mmid) 的時候，我們可以斷定 mid 一定在白點的左邊。

反證法：假設 mid 在白點的右邊，則 mmid 也一定在白點的右邊，又由 f(mid) < f(mmid) 可推出 mid > mmid，與已知沖突，故假設不成立。

同理，此時可以将 L = mid 來縮小範圍。

這是先增再減的模型 凸型

兩種寫法

int SanFen(int l,int r) //找凸點  
{  
    while(l < r-1)  
    {  
        int mid  = (l+r)/2;  
        int mmid = (mid+r)/2;  
        if( f(mid) > f(mmid) )  
            r = mmid;  
        else  
            l = mid;  
    }  
    return f(l) > f(r) ? l : r;  
}  
           

double three_devide(double low,double up)  
{  
    double m1,m2;  
    while(up-low>=eps)  
    {  
        m1=low+(up-low)/3;  
        m2=up-(up-low)/3;  
        if(f(m1)<=f(m2))  
            low=m1;  
        else  
            up=m2;  
    }  
    return (m1+m2)/2;  
}  
           

後面是先減再增 下凸

和上面反着來

int SanFen(int l,int r) //找凸點  
{  
    while(l < r-1)  
    {  
        int mid  = (l+r)/2;  
        int mmid = (mid+r)/2;  
        if( f(mid) > f(mmid) )  
            l = mid;  
        else  
            r = mmid;  
    }  
    return f(l) > f(r) ? l : r;  
}  
           

double three_devide(double low,double up)  
{  
    double m1,m2;  
    while(up-low>=eps)  
    {  
        m1=low+(up-low)/3;  
        m2=up-(up-low)/3;  
        if(f(m1)<=f(m2))  
            up=m2;  
        else  
            low=m1;  
    }  
    return (m1+m2)/2;  
}