一、概念:
一看三分便知道和是由二分演变而来,二分一般求单调区间的情况,而三分适合求凹凸函数,通常用来确定最值,三分是在二分基础上将右区间再分为两个区间。
二、算法步骤:
(1)先取整个区间的中间值 mid = (x+y)/ 2 ;
(2)再将右区间分为两个区间 midd = ( mid + y ) /2 ;
(3)然后比较 mid 与 midd 所形成的值那个最接近最值,如果 mid 接近则让 y = midd ,否则让 x = mid .
if (cal(mid) > cal(midmid)) right = midmid; else left = mid;
(4)重复(1)(2)(3)一直找到最值。
算法的正确性:
1、mid与midmid在最值的同一侧。由于凸性函数在最大值(最小值)任意一侧都具有单调性,因此,mid与midmid中,更大(小)的那个 数自然更为靠近最值。此时,我们远离最值的那个区间不可能包含最值,因此可以舍弃。
2、mid与midmid在最值的两侧。由于最值在中间的一个区间,因此我们舍弃一个区间后,并不会影响到最值
三、模版
const double EPS = 1e-10; double calc(double x) { // f(x) = -(x-3)^2 + 2; return -(x-3.0)*(x-3.0) + 2; } double ternarySearch(double low, double high) { double mid, midmid; while (low + EPS < high) { mid = (low + high) / 2; midmid = (mid + high) / 2; double mid_value = calc(mid); double midmid_value = calc(midmid); if (mid_value > midmid_value) high = midmid; else low = mid; } return low; }