cafelier@SRM

二分探索

23:09 |

みなさま二分探索ってどういう風に考えながらコードを書くのでしょうか、ということがちょっと気になりました。特に実数ではなくて整数のもの。問題：

private int X = 1 以上 9_9999_9999 以下の秘密の整数;
bool query(int x) { return X <= x; }

X を直接読まずに query() 関数を何回か呼び出すことで X を求めなさい。

自分の場合、こう考えながら書いています。

int solve()
{
  int L = 0;            // 条件を満たさないとわかっている数を適当に
  int R = 10_0000_0000; // 条件を満たすとわかっている数を適当に

  // 不変条件: 「常に答えは半開区間 (L, R] の範囲にある」

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。

以下、意地でもこの条件を崩さないことだけを念頭においてコーディング。（重要なので二回）

  while( R-L > 1 ) // 答えの範囲が整数一つになるまで繰り返し
  {
     int C = (L+R)/2; // 二分探索なので真ん中をとる

     (query(C) ? R : L) = C;
     // (query(C) ? L : R) = C; ではない。(L,R] が答えの範囲なので R が条件満たす方、L が満たさない方
  }

  return R; // 答えは (L,R] にあるのだから L じゃなくて R が答え
}

Topcoderにサブミットした二分探索のコード全部に半開区間の不変条件がコメントで書いてあります。これを念じていないと「ループ終了条件」「どっちの場合にLとRのどっちを更新するんだっけ？」「最後に返す値はどれ？」の３カ所で、USB端子の差し込み方向並に毎回迷ってしまうので。

チャレンジフェーズで他の人のコードを見ていると、違う考え方でコード書いている人が結構多いようなので興味が湧いています。if(query(C)) R=C; else L=C+1; みたいな形の更新式になるコードとか。気になります。

追記：反応集 http://togetter.com/li/331840