二分探索

ある条件を満たす最小(最大)の値を求めるような問題に適用できる。

//整数値の場合
int l = -INF, u = INF;
while(u-l>1){
  int m = (u+l)/2;
  if(mが条件を満たす) u=m; //解は(l,m]
  else l=m; //解は(m,u]
}


//小数値の場合
double l = -INF, u = INF;
for(int i=0; i<100; i++){
  double m = (u+l)/2;
  if(mが条件を満たす) u=m;
  else l=m;
}