三分查找--

叁歲伎倆 2022-10-08 02:20 128阅读 0赞

我们都知道 二分查找 适用于**单调函数**中逼近求解某点的值。

如果遇到凸性或凹形函数时（非单调），可以用三分查找求那个凸点或凹点。

下面的方法应该是三分查找的一个变形。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]

如图所示，已知左右端点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;  
    }

https://blog.csdn.net/pi9nc/article/details/9666627

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]: /images/20221005/a14133ab41dc4588a7f8232c32b1239f.png