▼はじめに

みなさん、二分探索しているでしょうか。(？)

二分探索とは、ソート済み配列に対する探索アルゴリズムの一つで、

膨大なデータに対しても高速に動作するのが魅力ですよね。

しかし、いざ二分探索をプログラムで書こうとすると、

度々バグが発生したり、応用の仕方がわからなかったりといったことが起こります。

（私は起こりました。）

そこで、バグが起こりにくく、応用も簡単にできる、

「めぐる式二分探索」というものをご紹介します。

▼二分探索の応用

その前に二分探索の応用のついてお話しします。

二分探索には「ソート済み配列から目的の値を見つける」という使い方の他に、

「ある条件を満たす範囲の最大値 or 最小値を見つける」ということもできます。

例えば以下のような配列を考えます。

1 2 3 4 7 8 9

ここで「ある条件」を「値が6以上」と設定すると

以下のように色分けをすることができます。

1 2 3 4 7 8 9

青い部分が「ある条件」を満たす範囲（値が6以上）で、

赤い部分が「ある条件」を満たさない範囲（値が6未満）となります。

後は二分探索を用いてこの境目を見つけることさえできれば、

青い部分の最小値と赤い部分の最大値を見つけることができます。

この例だと、値が6以上かつ最小の値は7、値が6未満かつ最大の値は4であることがわかります。

これが二分探索の応用になります。

▼めぐる式二分探索

二分探索には様々な実装方法が存在するのですが、

その中の一つが「めぐる式二分探索」になります。

めぐる式二分探索を使用すると以下のようなメリットがあります。

・バグが発生しにくいこと

・先ほどの「応用」の考え方を踏襲していること

終了条件や更新時の値もテンプレ化されているため、

バグに気をつける必要性があまりないことが利点です。

そのテンプレートは以下のようになっています。

ok = N;
ng = -1;

while(abs(ok - ng) > 1)
{
  mid = (ok + ng) / 2;
  if(solve(mid))
  {
    ok = mid;
  }
else
  {
    ng = mid;
  }
}  

ただし、Nは配列の要素数、absは絶対値を返す関数、solveはmidが条件を満たすかを判定する関数です。

midが条件を満たす場合はokの値をmidで更新し、

midが条件を満たさない場合はngの値をmidで更新するような、非常にシンプルな仕組みになっています。

また、探索終了時には必ずokとngの位置が隣り合うようになるため終了条件も明確です。

▼具体例

最後に具体例を通して「めぐる式二分探索」の動きを見ていきます。

2 3 5 6 7 8 9

このようなソート済み配列から3の位置を調べたいとします。

ここである条件を以下のように設定します。

・条件を満たす(OK)：3以上

・条件を満たさない(NG)：3未満

これで実際の動きを見てみます。

– 2 3 5 6 7 8 9 –

青色がOK、赤色がNGの場所を指しています。

はじめはOKとNGの位置は配列外としておきます。

 – 2 3 5 6 7 8 9 –

OK=7とNG=-1の平均は3なので、6が条件を満たすかどうかを調べます。

 – 2 3 5 6 7 8 9 –

6は3以上であるため条件を満たします。

よって、6より右側はすべて条件を満たすことがわかりました。

 – 2 3 5 6 7 8 9 –

OK=3とNG=-1の平均は1なので、3が条件を満たすかどうかを調べます。

 – 2 3 5 6 7 8 9 –

3は3以上であるため条件を満たします。

よって、3より右側はすべて条件を満たすことがわかりました。

 – 2 3 5 6 7 8 9 –

OK=1とNG=-1の平均は0なので、2が条件を満たすかどうかを調べます。

 – 2 3 5 6 7 8 9 –

2は3以上ではないため条件を満たしません。

よって、2より左側はすべて条件を満たさないことがわかりました。

OK=1とNG=0の差の絶対値が1以下となったため探索終了です。

OKの位置を見ると値が3であることが確認できます。

（厳密には3以上の要素の中で最小のものが求まります。）

▼終わりに

いかがだったでしょうか。

二分探索でバグが発生する、応用がなかなかできないという方は

是非めぐる式二分探索を活用していただけたらと思います。

名前の由来↓

【めぐるのアルゴリズム講座】
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l

— 因幡めぐる@競技プログラミング (@meguru_comp) February 9, 2016