前言
前面我们已经学习了二分算法。其实，对于一些特定问题，我们还可以使用三分算法。

程序设计思路
三分，顾名思义，就是把数据分成三段，使用四个指针，其基本方向仍是缩小范围。我们可以重复检查左中指针与右中指针，判断答案在哪一侧，将左指针或右指针移动到中指针，再重新计算左右中指针，实现缩小范围。
三分算法主要适用于曲线形函数的求解，因为这类题目一般都是求其在峰上的值。

代码实现
直接看题目：

题目要求很清楚：求函数值为峰值时，x的值，看代码——

#include <bits/stdc++.h>
using namespace std;

double n,l,ml,mr,r,iq[13];//l、ml、mr、r分别为左、左中、右中、右指针。iq数组存放系数

double f(double x){//即check，验证函数
    double ans=0;
    for(int i=0;i<=n;i++) ans+=iq[i]*pow(x,n-i);
    return ans;
}

void sett(){//重算左中、右中指针
    ml=l+(r-l)/3;
    mr=l+((r-l)/3)*2;
    return ;
}

int main(){//输入输出，不解释
    scanf("%lf%lf%lf",&n,&l,&r);
    for(int i=0;i<=n;i++) scanf("%lf",&iq[i]);
    while(fabs(l-r)>1e-5){
        sett();
        if(f(ml)>f(mr)) r=mr;
        else l=ml;
    }
    printf("%.5lf",ml);
    return 0;
}

由此可见，三分实质上就是二分加上了一个指针，从而使答案限制在峰顶，最后求出结果。

结语
相比于二分，三分的应用场景小了很多。不过对三分的学习，其实也可以当成对二分的复习。我是faryou，再见！

前言
事实上，我们在解决实际问题时一般会用二分答案而不是二分查找。今天我就来给大家介绍一下二分查找这种由二分法衍生出来的办法。

程序设计思路
相比于二分查找，二分答案有极为重要的一点不同——check思想。也就是说，每查到一个答案都将其经过特定的程序后再与基准数比较。这样看来，二分答案其实就是在二分查找的基础上加了一步检查。
二分查找往往是在一堆数里查找答案，而二分答案则通常面对一个范围，这也是它们之间的一显著区别。

代码实现
解方程中经常会用到二分答案，因为它的范围很广，而且往往包含浮点数答案。来看下面这题：

    这题目明摆着要我们用二分答案，否则如果用浮点数试过去效率太低，容易TLE。看代码：

#include <bits/stdc++.h>
double a,b,c,d,l,m,r;//a、b、c、d如题意，l、m、r分别为左、中、右指针
double f(double x){//检查解是否合法，算一遍方程
    return a*pow(x,3)+b*pow(x,2)+c*x+d
}
int main(){
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    for(int i=-100;i<100;i++){//由题意得有200个整数区间，分别查找
        l=i;
        r=i+1;
        if(f(l)==0){//特判，正好相等时直接输出
            printf("%.2lf ",l);
            continue;
        }
        if(f(l)*f(r)>=0) continue;//用题目中所给式子判断
        while(r-l>0.001){//不断缩小范围
            m=(l+r)/2;
            if(f(l)*f(m)<=0) r=m;
            else l=m+0.001;
        }
        printf("%.2lf ",m);
    }
    return 0;
}

代码中的f()函数就是所谓check思想。这样一来便很好理解了。

结语
二分答案作为二分算法的一个衍生分支，能够解决很多问题。我是faryou，再见！

前言
在信奥中，二分算法是一种非常重要的方法。利用它，我们在某些场合中寻找数时就不必要遍历数组，大大提高了效率。今天我们来学习二分算法的基本方法。

程序设计思路
有这样一个问题：给你一个数组，数组里面的数已经按数值大小倒序排列，请从中找到某个数，要求不得遍历数组。
这里需要注意，数组里的数已经降序排列，这一点对我们要进行的查找是有帮助的。我们可以利用数之间的大小关系，进行查找。比如说，可以先找到数组中间的那个数，与基准数（要找的数）进行比较。如果基准数大于这个数，那么我们就可以确定基准数在这个数的左侧，反之则在这个数的右侧。这样一直循环，直到找到基准数。
这就是二分查找的精髓。

代码实现
直接看题：

这是二分算法的模板题，思路已经有了，直接上代码——

#include <bits/stdc++.h>
int a[1000005],n,m,aq;//a存输入的数据，n、m同题意，aq临时存要查找的数
int search(int iq){
    int left=1,right=n,mid=(1+n)/2;//确定左指针、右指针、中央
    while(left<right){//当左右指针相遇时，循环结束
        mid=(left+right)/2;
        if(a[mid]>=iq) right=mid;
        else left=mid+1;
    }//不断更新左、右、中指针
    if(a[left]==iq) return left;
    else return -1;
}

int main(){//main里全是输入和输出，不讲了
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d",&aq);
        printf("%d ",search(aq));
    }
    return 0;
}

可以看到，这里使用了左右两个指针解决问题。程序并不难写，关键在思路。

总结
二分算法是一种能够大大提升查找效率的方法。之后我还会为大家带来由二分算法衍生出的二分答案和三分算法。我是faryou，再见！