从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的!

简单点说二分是查找区间,相当于一次函数,三分就是二次函数了,求它的极值,怎么做,数学常用的是求导,计算机就用查找咯,那么请看下面的简单概述吧!

一. 概念

在二分查找的基础上,在右区间(或左区间)再进行一次二分,这样的查找算法称为三分查找,也就是三分法。

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

二分查找所面向的搜索序列的要求是:具有单调性(不一定严格单调);没有单调性的序列不是使用二分查找。

与二分查找不同的是,三分法所面向的搜索序列的要求是:序列为一个凸性函数。通俗来讲,就是该序列必须有一个最大值(或最小值),在最大值(最小值)的左侧序列,必须满足不严格单调递增(递减),右侧序列必须满足不严格单调递减(递增)。如下图,表示一个有最大值的凸性函数:

二、算法过程

(1)、与二分法类似,先取整个区间的中间值mid。

mid = (left + right) / 2;

(2)、再取右侧区间的中间值midmid,从而把区间分为三个小区间。

midmid = (mid + right) / 2; 

(3)、我们mid比midmid更靠近最值,我们就舍弃右区间,否则我们舍弃左区间?。

比较mid与midmid谁最靠近最值,只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时,mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。 

if (cal(mid) > cal(midmid))  
     right = midmid;  
else  
      left = mid;  

(4)、重复(1)(2)(3)直至找到最值。

(5)、另一种三分写法

 1 double three_devide(double low,double up)
 2 {
 3     double m1,m2;
 4     while(up-low>=eps)
 5     {
 6         m1=low+(up-low)/3;
 7         m2=up-(up-low)/3;
 8         if(f(m1)<=f(m2))
 9             low=m1;
10         else
11             up=m2;
12     }
13     return (m1+m2)/2;
14 }

算法的正确性:

1、mid与midmid在最值的同一侧。由于凸性函数在最大值(最小值)任意一侧都具有单调性,因此,mid与midmid中,更大(小)的那个 数自然更为靠近最值。此时,我们远离最值的那个区间不可能包含最值,因此可以舍弃。

2、mid与midmid在最值的两侧。由于最值在中间的一个区间,因此我们舍弃一个区间后,并不会影响到最值

 1 const double EPS = 1e-10;
 2 double calc(double x)
 3 {
 4     // f(x) = -(x-3)^2 + 2;
 5     return -(x-3.0)*(x-3.0) + 2;
 6 }
 7 
 8 double ternarySearch(double low, double high)
 9 {
10     double mid, midmid;
11     while (low + EPS < high)
12     {
13         mid = (low + high) / 2;
14         midmid = (mid + high) / 2;
15         double mid_value = calc(mid);
16         double midmid_value = calc(midmid);
17         if (mid_value > midmid_value)
18             high = midmid;
19         else
20             low = mid;
21     }
22     return low;
23 }

调用ternarySearch(0, 6),返回的结果为3.0000

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

如果遇到凸性或凹形函数时,可以用三分查找求那个凸点或凹点。

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

如图所示,已知左右端点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 来缩小范围。

 1 int SanFen(int l,int r) //找凸点
 2 {
 3     while(l < r-1)
 4     {
 5         int mid  = (l+r)/2;
 6         int mmid = (mid+r)/2;
 7         if( f(mid) > f(mmid) )
 8             r = mmid;
 9         else
10             l = mid;
11     }
12     return f(l) > f(r) ? l : r;
13 }

 日后会以例题的形式进行详细的讲解,这个也就是入门级!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

python数据分析师面试题选

python数据分析部分 1. 如何利用SciKit包训练一个简单的线性回归模型 利用linear_model.LinearRegression()函数 #...

5666
来自专栏C语言及其他语言

【每日一题】1445: [蓝桥杯][历届试题]最大子阵

节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

3828
来自专栏ml

nyoj-----幸运三角形

幸运三角形 时间限制:1000 ms  |  内存限制:65535 KB 难度:3 描述         话说有这么一个图形,只有两种符号组成(‘+’或者‘-’...

30110
来自专栏算法channel

图算法|Prim算法求最小生成树

01 — 一个实际问题 要在n个城市之间铺设光缆,要求有2个: 这 n 个城市的任意两个之间都可以通信; 铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,...

9167
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

3602
来自专栏Phoenix的Android之旅

一张图看懂开发和运营的思维差别

用Dijkstra算法很简单,我们需要 · 用 6*6矩阵 source[6][6]表示点之间的距离,也就是图中的权值 · 自己与自己的距离为0,无直接连接的距...

761
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

3481
来自专栏bboysoul

1475: C语言实验题――一元二次方程 II

描述:求一元二次方程ax2+bx+c=0的解。a,b,c为任意实数。 输入:输入数据有一行,包括a b c的值 输出:按以下格式输出方程的根x1和x2。x1...

1213
来自专栏机器学习原理

我的机器学习numpy篇何为ndarray?ndarry创建生成正态分布ndarry属性修改形状ndarry运算ndarry切片矩阵转置聚合函数

前言: numpy是以矩阵为基础的数学计算模块,其基础为多维数组为ndarray 官方文档:(https://docs.scipy.org/doc/nump...

3918
来自专栏数据科学学习手札

(数据科学学习手札03)Python与R在随机数生成上的异同

随机数的使用是很多算法的关键步骤,例如蒙特卡洛法、遗传算法中的轮盘赌法的过程,因此对于任意一种语言,掌握其各类型随机数生成的方法至关重要,Python与R在随机...

2907

扫码关注云+社区

领取腾讯云代金券