信息学奥赛算法专题：三分查找搜索算法的步骤及代码

原标题：信息学奥赛算法专题：三分查找搜索算法的步骤及代码

三分法的定义

在二分的查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找。

三分法的应用场景

三分法查找通常用来迅速确定最值。

三分法使用要求

无论是二分查找还是三分查找，都需要满足单调性（序列是递增还是递减），如果不满足将不能使用二分/三分。

三分法所面向的搜索序列的要求是：序列为一个凹凸函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足严格单调递增（递减），右侧序列必须满足严格单调递减（递增）

补充知识

因为口口老师教的学生大部分都是小学生，考虑到他们并没有学习函数相关知识，简单补充一点。

二次函数的基本表示形式为y=ax²+bx+c（a≠0）。二次函数最高次必须为二次， 二次函数的图像是一条对称轴与y轴平行或重合于y轴的抛物线

（当a>0时，开口朝上，拥有最小值）

（当a<0时，开口朝下，拥有最大值）

在教学的过程当中，肯定还有很多小朋友对此不能很好理解，在这里安利一个数学画图网站：https://www.desmos.com/，输入函数表达式即可生成图像，并且改系数即可拥有不同图形效果。

三分查找实现步骤

（1）先取整个区间的中间值mid

mid=(left+right)/2;

（2）再取右侧区间的中间值midmid，从而把区间分为三个小区间。

midmid=(mid+right)/2;

（3）我们mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间。

比较mid与midmid谁最靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。（画图才是王道，很多不能理解的只需要把图画出来，就很好理解了）

（4）案例实现

以上思路参考了《三分查找》，但也对代码按照我自己的理解，进行了修改，也方便给学生解释。

另外一种取值方法

lmid与rmid的取值：一般可以将这两个点取为[l,r]的三等分点。即

lmid=l+(r-l)/3.0;rmid=r-(l-r)/3.0;

信息学本身是一门比较难的学科，很多学生会因为老师讲的不够详细，不够透彻，而心生怯意。在上课时，喜欢给学生讲多种方法，看他们能够接受哪一种。

案例应用

明明做作业的时候遇到了 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

福利分享

（复赛入门提高必背算法模板）

获取方法：vx关注scratch-coco之后，回复“c++”，按照步骤即可领取。

返回搜狐，查看更多

责任编辑：