二分探索 (binary search)は、全順序集合$S$に対し単調な関数$f : S \rightarrow \{0,1\}$が与えられた時、$f(x) = 1$となる最小の$x$を見つける、あるいは近似するアルゴリズムである。

(だれか加筆してください)

・探索対象
f(x) >= [F_TERGET]となる最小値[x]を調べる
xは整数としてみる。

・目的関数f(x)が満たす条件
f(x)は単調増加関数。(_)
f(x) <= f(x+|α|)

・初期区間の区間端が満たす条件
[NG,OK]	(NG<=OK)
//[NG]の設定
NG = 0;//適当に入れてる
/*//やったことない
NG = 0;
sub = -1;//sub<0	減少方向に持っていく
while( f(NG) >= F_TERGET ){
	NG += sub;//オバフロ
	sub *= 2;//オバフロ
}
*/
//f(NG) < F_TERGET が成立する値[NG]
//f(NG) >= F_TERGET が成立しない値[NG]
/*
f(-inf)>=F_TERGET
の場合はどうなるんだろうね？
*/

//[OK]の設定
OK = 1;
while( f(OK) < F_TERGET ){
	OK *= 2;//オーバーフロー
}
/*//区間が負の場合に出会ったことが無い
OK = 1;
add = 1;//add>0増加方向に持っていく
while( f(OK) < F_TERGET ){
	OK += add;//オーバーフロー
	add *= 2;//オーバーフロー
}
*/
//f(OK) >= F_TERGET	が成立する値[OK]
//f(OK) < F_TERGET が成立しない値[OK]

・1step
while(OK-NG>1 /*続行条件*/)
{
	//中央値の取得
	mid = (OK+NG)/2;//オーバーフローに注意NG+(OK-NG)/2
	F_mid = f(mid);//fの計算オーダー
	
	//判定
	if( F_mid < F_TERGET ){
		//区間[NG,mid]上にF_TERGETはない。f([NG,mid]) < F_TERGET
		//f(x)<[F_TERGET]が成立する最大値[x]は、[mid]以上
		//f(x)>=[F_TERGET]が成立しない最大値[x]は、[mid]以上
		NG = mid;
	}
	else{//F_mid >= F_TERGET;
		//区間[mid,OK]上にF_TERGETはある。f([mid,OK]) >= F_TERGET
		//f(x)>=[F_mid]が成立する最小値[x]は、[mid]以下
		OK = mid;
	}
	/*
	調べる区間が[NG,OK]から
	[NG,mid]又は[mid,OK]に変更される。
	この1stepで区間は半分ぐらいになる。
	*/
}
答えは[OK]