[ Ternary Search ] 三分搜尋法模板

對於一個U型或倒U型函數，我們可以利用三分搜尋法找出其最低/最高點，時間複雜度為$\ord{log \; n}$,這裡n是$10^{(整數位數+浮點位數)}$

關於原理就不多說了，以下提供對於U型函數的模板:

	/*
	f是傳入的函數，eps表示精準度，通常設為1e-5
	l,r為邊界，所以必須先預估出極值點的位置
	*/
	template<typename _F>
	inline double ternary_search(_F f,double l,double r,double eps){
	static double m1,m2;
	while(r-l>eps){
	m1=l+(r-l)/3;
	m2=r-(r-l)/3;
	if(f(m1)>f(m2))l=m1;/*如果對象是倒U型函數，則改成 < */
	else r=m2;
	}
	return (l+r)/2;
	}

view raw ternary_search.cpp hosted with ❤ by GitHub

用法:

	inline double f(double x){
	return x*x-2*x+1;
	}
	/*假設邊界為-10~10*/
	printf("%.5f\n",ternary_search(f,-10,10,1e-6));

view raw use_way.cpp hosted with ❤ by GitHub