三分查找

運用要求

僅僅適用於單峰函式。

作用

查找凸性函式峰頂的位置。

解析

三分查找

三分查找與二分查找一樣，它會不斷縮小答案所在的求解區間。二分法縮小區間利用的原理是函式的單調性，而三分法利用的是函式的單峰性。設當前求解的區間為[l,r]，令m1=l+(r-l)/3,m2=r-(r-l)/3。求出函式值f(m1)和f(m2)。若f(m1)比f(m2)更好（我們把函式值最優的那個值稱為好值，若計算最大值，則f越大越好。）若f(m1)更好則r=m2,否則l=m1。不斷縮小求解範圍，直到區間為唯一解。

時間複雜度

O(log2/3(n))

代碼

C++

​1 2 3 4 5 6 7 8 9 10 11 12

​template<typenamename>nameternary_search(longlong(*good)(namedep),namel,namer,nameprecision) { namedifference,one,two; while(r-l>=precision) { difference=(r-l)/3; one=l+difference,two=r-difference; if(good(one)<good(two))l=one+1; elser=two-1; } returnl; }