アルゴリズムメモ

ある区間内に解が存在することが明白でかつその区間で単調増加または単調減少の場合は、その関数はソート済みの配列と見なせるのでバイナリサーチの要領で解を探索する。
具体的には区間(a,b)でf(a)*f(b)<-1かつ、df(x)=kの場合でf(x)=0となる解を探索する場合以下のようにする。ここでkは0でない。

c=(a+b)/2;
eps=1.0e-6; //許容誤差
while(abs(f(c))>eps){
	if(abs(f(a))>abs(f(b))){
		a=c;
	}else if(abs(f(a))<abs(f(b))){
		b=c;
	}else{
		break;
	}
	c=(a+b)/2;
}

ここでabs(x)はxの絶対値を返す。解はcに格納される。事前に単調増加か単調減少かがわかっているのなら絶対値計算の必要はない。