信息学奥赛算法专题：三分查找搜索算法的步骤及代码
2023-06-14 08:53阅读：
三分法的定义
在二分的查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找。
02—
三分法的应用场景
三分法查找通常用来迅速确定最值。
03
—
三分法使用要求
无论是二分查找还是三分查找，都需要满足单调性（序列是递增还是递减），如果不满足将不能使用二分/三分。
三分法所面向的搜索序列的要求是：序列为一个凹凸函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足严格单调递增（递减），右侧序列必须满足严格单调递减（递增）
03
—
补充知识
因为口口老师教的学生大部分都是小学生，考虑到他们并没有学习函数相关知识，简单补充一点。
二次函数的基本表示形式为y=ax²+bx+c（a≠0）。二次函数最高次必须为二次，
二次函数的图像是一条对称轴与y轴平行或重合于y轴的抛物线
（当a>0时，开口朝上，拥有最小值）
（当a<0时，开口朝下，拥有最大值）
在教学的过程当中，肯定还有很多小朋友对此不能很好理解，在这里安利一个数学画图网站：https://www.desmos.com/，输入函数表达式即可生成图像，并且改系数即可拥有不同图形效果。
03
—
三分查找实现步骤
（1）先取整个区间的中间值mid
mid=(left+right)/2;
（2）再取右侧区间的中间值midmid，从而把区间分为三个小区间。
midmid=(mid+right)/2;
（3）我们mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间。
比较mid与midmid谁最靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。（画图才是王道，很多不能理解的只需要把图画出来，就很好理解了）
（4）案例实现
#include
using
namespace
std;
const
double
eps=10e-9;//对双精度数值来说eps表示从
1.0
到下一个最大双精度数的距离
double
f(double
x){
return
x*x*x-3*x*x-3*x+1;
//凸函数
}
double
three(double
left,double
right){
double
mid=0,mmid=0;
while(left+epsmid=(left+right)/2;
mmid=(mid+right)/2;
if(f(mid)>f(mmid)){
right=mmid;
}else{
left=mid;
}
}
return
f(mid);//}
int
main(){
cout<<three(-0.9981,0.5);
return
0;
//其输出结果为1.65685
}
以上思路参考了《三分查找》，但也对代码按照我自己的理解，进行了修改，也方便给学生解释。
04
—
另外一种取值方法
lmid与rmid的取值：一般可以将这两个点取为[l,r]的三等分点。即
lmid=l+(r-l)/3.0;rmid=r-(l-r)/3.0;
信息学本身是一门比较难的学科，很多学生会因为老师讲的不够详细，不够透彻，而心生怯意。在上课时，喜欢给学生讲多种方法，看他们能够接受哪一种。
04
—
案例应用
明明做作业的时候遇到了 n 个二次函数 Si(x)= ax^2 + bx + c，他突发奇想设计了一个新的函数 F(x)
= max{Si(x)}, i = 1、2、3、......、 n。明明现在想求这个函数在 [0,1000]
的最小值，要求精确到小数点后四位，四舍五入。
Input
输入包含 T 组数据，每组第一行一个整数 n；接下来 n 行，每行 3 个整数 a, b, c
，用来表示每个二次函数的 3 个系数。
Output
每组数据输出一行，表示新函数 F(x) 的在区间 [0,1000]
上的最小值。精确到小数点后四位，四舍五入。
Sample Input
- 2
1
2 0 0
2
2 0 0
2 -4 2
- Sample Output
- 0.0000
0.5000
#includeusing
namespace
std;const
int
N=1e5+5;const
double
inf=1e9;const
double
eps=1e-9;double
a[N],b[N],c[N];int
n;
double
f(double
x){
double
mx=eps;
for(int
i=1;i<=n;i++){
mx=max(mx,a[i]*x*x+b[i]*x+c[i]);
}
return
mx;}
double
three(int
left,int
right){
double
l=left,r=right;
//第一种写法：//
double mid=0,mmid=0;//
while(l+eps//
mid=(l+r)/2;//
mmid=(mid+r)/2;//
if(f(mid)>f(mmid)){//
l=mid;//
}else{//
r=mmid;// }//
}
//第二种写法：
double
lmid=0,rmid=0;
while(l+eps
lmid=l+(r-l)/3.0;
rmid=r-(l-r)/3.0;
//判断lmid,rmid谁离最小值近，画个凹函数图更好理解，
if(f(lmid)r=rmid;
}else{
l=lmid;
}
}// return
f(mid);
return
f(l);}
int
main(){
int
t;
cin>>t;
while(t--){
cin>>n;
for(int
i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
}
printf('%.4lf',three(0,1000));
}}
04
—
福利分享
（复赛入门提高必背算法模板）
获取方法：vx关注scratch-coco之后，回复“c++”，按照步骤即可领取。
