二分法

SRM462 div2 medium
二分検索でもよく使う方法．

seek  //入力
low = 0; high = 100
while(1) {
  int mid;
  mid = (low+high)/2;
  int calc = ...;  //何らかの処理(midを仮引数に関数の戻り値を使用)
  if(calc > seek) {  ///中間の値が大きい->high(最大値)を下げれば良い．
    ....
    high = mid;
  if(calc == seek) {
    ans = mid;
    break;  
  if(calc < seek) {  //中間の値が小さい=>low(最小値)を挙げれば良い．
    ....
    low = mid;
  }
}
return ans;

//誤差1e-9までの範囲でOKといわれれば、fabs(calc-seek) < EPS;  ->その他  で処理

SRM462

  double getRadix(int age, string candlesLine) {
    int pos = 0;
    while(candlesLine[pos] == '0') {
      pos++;
    }
    candlesLine = candlesLine.substr(pos);
    if(candlesLine == "1") {
      return (age==1) ? -2.0 : -1.0;
    }
    int len = candlesLine.length();
    if(len == 0) { return -1.0; }
//ここから。
    double hi = 100; double lo = 0;
    double mid;
    while(1) {
      mid = (hi+lo)/2;
      DG(mid);
      double tmp = 0;
      for(int i = 0; i < len; i++) {
	if(candlesLine[len-i-1] == '1') {
	  tmp += pow(mid, i);
	}
	if(tmp > 1000) break;
      }
      if(fabs(tmp - age) < eps) {
	break;
      } else if(tmp > age) {
	hi = mid;
      } else if(tmp < age) { lo = mid; }
    }
    return mid;
  }