注：学习三分之前，建议先学习掌握二分。如有未进行了解或者不理解二分，可以前往查看我之前的博客，有详细的二分思路和模板代码可供参考学习。博客链接：【算法详解】二分查找完全指南：从题目识别到拒绝死循环的通用模板（附 C++ 模板）-CSDN博客

我们知道，二分查找首先就是需要保证我们进行查找的区域必须是单调的。如果不单调，我们就无法直接判定我们二分的当前一半区域是否全部不符合我们的标准，从而无法直接舍弃一半的搜索区间。

但是现在，我们需要解决的问题就是二分无法解决的了：在一个单峰函数中，找到一个最大/最小值点。如下图的单峰函数。

很显然，二分此时无法解决了（实际上可以二分导数，但这里暂不讨论）。我们无法确定二分到的左半边和右半边是否可以直接舍去不看。为了解决这个找单峰函数最值问题，我们要用到三分查找这个方法。细分下来，可以分成实数三分和整数三分，二者有一点细微差别。实数三分就是整个实数域内进行的三分，是有小数的，所以我们需要判定精度是否足够；整数三分是只在整数内进行三分，没有了小数，但最终的三分结束必须对答案进行一点判定。

实数三分

洛谷题目链接：P3382 三分 - 洛谷

以洛谷 P3382 为例（此题是先增后减求最大值，先减后增求最小值同理符号反向即可），这题很明显已经告诉我们要在它给出的函数中找到最值。接下来我们就详细分析一下三分如何解决。

顾名思义，二分我们是直接将区间对半分，三分就是将搜索区间等分成三个部分。左三等分点我命名为 f1 ，右三等分点命名为 f2 。而区间左边界是 l ，右边界是 r ，分成三个区间 [l,f1] [f1,f2] [f2,r] 。

分成三个部分的原因是什么呢？二分我们分成两个部分，中间 mid 点。在具有单调性的区间里，我们能够轻松判定左半边或者右半边哪一边是有我们想要的答案，哪一边是完全不符合而舍去的；但放在单峰函数里，如果我们还是只有一个 mid 点，我们无法判定最值到底在左边还是在右边。

而三分在此处有两个分割点 f1 和 f2 ，分成三个部分。我们分情况看看为什么三分可行。F1 和 F2 分别代表 f1 和 f2 对应的函数值。

F1 > F2

f1 和 f2 的位置情况此时仅有两种可能性。

在这个时候，f2 可以在最值左右两侧都行，是不确定的。我们能确定的是 f1 左侧区间 [l,f1] 绝对没用了，因为要满足 F1>F2 ，f1 就必须在最值左边。所以我们可以直接舍弃 f1 左侧区间，即在代码中执行：l = f1 。

F1 < F2

f1 和 f2 的位置情况此时也仅有两种可能性。

可以发现，和上一个情况几乎就是同理了。 f2 可确定而 f1 不可确定，所以 f2 右侧区间 [f2,r] 可以舍去。即在代码中执行：r = f2 。

F1 = F2

如果是 F1=F2 ，那情况就更简明了。此时 F1 和 F2 要么同时等于最值，要么同时分立在最值左侧和右侧，所以只有 [f1,f2] 区间需要保留，而另外的区间可以直接舍去。即在代码中同时执行：l = f1；r = f2 。

但问题是，double 类型数据完全相等概率极低，所以这个分支我们完全可以不写，因为它是两侧区间随意去掉哪个都可以的。这里的说明仅是让我们的逻辑更完整。

三分的原理并不难，主要是边界情况的判定容易出错。在实数域内三分，我们只需要保证精度问题即可。在这道题中，题目要求是误差在不超过 $10^{-5}$ ，所以循环条件可以写 r-l>1e-6 或者更小，确保不会出现精度问题。 另外的问题就是对于这种 n 次函数多项式的计算，我们可以采用秦九韶算法来减少精度误差。

秦九韶算法是对于多项式

可写成

这样计算可以减少乘法次数，避免乘法次数过多带来的精度误差。

解决了这些，题目就很简单了。下面是个人代码。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
double l,r;
double arr[15];
double ans;
double f(double x){
    double ans=0;
    //秦九韶算法
    for(int i=n;i>=1;--i){
        ans+=arr[i];
        ans*=x;
    }
    return ans+arr[0];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>l>>r;
    for(int i=n;i>=0;--i) cin>>arr[i];//个人习惯倒序读入，索引对应幂次
    while(r-l>1e-6){
        double f1=l+(r-l)/3;
        double f2=r-(r-l)/3;
        //利用f函数算出具体值
        double F1=f(f1);
        double F2=f(f2);
        if(F1<F2) l=f1;//如果求最小则r=f2
        else r=f2;//如果求最小则l=f1
    }
    cout<<fixed<<setprecision(5)<<l;//此时l和r都可作为答案，误差允许，随意输出一个即可
}

整数三分

整数三分是最容易出现死循环的。和刚刚的实数三分不同，实数三分可以说是一个连续的函数，而整数三分因为只考虑整数点，是离散的一些点，所以相比于刚刚略有不同。

不同的地方主要是在终止条件上。实数三分由于精度误差，只要达到我们精度误差要求即可；而整数三分的问题就是，我们终止条件理所当然地认为应该是找到最值就结束，但事实却不能这样。

如果我们要使得 l>r 才终止循环，我们可以发现，当区间剩下小于三个点时，我们将进入死循环。此时，(r-l)/3 一直算出来都是 0 了。也就是说，算出来的 f1 等于 l ，f2 也等于 r 。这样我们的区间永远都收缩不下去了，形成死循环。

为了避免这种情况发生，我们可以将循环条件定为 r-l>2 。这样规定，我们可以保证我们的区间 [l,r] 永远都是有大于 3 个点，从而有效避免了死循环。但我们循环进行完毕后，不能像实数三分一样直接取 l 或者 r 作为最值点，还需要进行对 [l,r] 的遍历，找出那个真正的最值。

所以实际上，整数三分唯一容易死循环的点就在于循环条件而已。只要了解了这个原因，相信大家不会犯这样的错误。由于我找不到有整数三分的模板题，我就还是沿用 P3382 的题目，写一个整数三分，示例如下，只给出主要的代码块。

while(r-l>2){
        int f1=l+(r-l)/3;
        int f2=r-(r-l)/3;
        //利用f函数算出具体值
        int F1=f(f1);
        int F2=f(f2);
        if(F1<F2) l=f1;//如果求最小则r=f2
        else r=f2;//如果求最小则l=f1
    }
//遍历当前区间求最值
int ans=l;
for(int i=l+1;i<=r;++i){
    //如果是最小则符号相反
    if(f(ans)<f(i)){
        ans=i;
    }
}