二分探索

ちょっと二分探索の挙動で気になったことがあったので書いておく。挙動というのは指定した値が見つからなかった時や同じ値が複数存在した時にどうなるかということだ。

配列内を探索するならSTLのlower_boundとupper_boundを使えばいいだけの話なのだが、最近、広義単調増加関数の値を二分探索することも結構あるので自分で迷わず書けるになっておく必要がある。


まず、STLの二分探索関数の仕様について。プロトタイプを書いてみたので雰囲気で理解して欲しい。

itr lower_bound(itr first, itr last, value_t value)
itr upper_bound(itr first, itr last, value_t value)
bool binary_search(itr first, itr last, value_t value) 

ついでなのでvalueがコンテナ内にあるかないかだけを判断するだけの使えない仕様のbinary_searchも書いておいた。
指定した値valueが見つかった場合は、lower_boundはvalueと同値になる範囲の最初のイテレータ、upper_boundはvalueと同値になる範囲の最後の次のイテレータを返す。
valueが見つからなかった時はlower_bound,upper_boundともに
valueより大きな最初の要素のイテレータを返す。これはequal_rangeでの使い方を考えればもっともな仕様なのだが、lower_boundの言葉のニュアンスから受ける印象とはちょっと異なるので注意が必要だ。


で、今回自分が書いたコード。テストはf(x)をx*xにしたときとx/3にした時でSTLの関数の挙動と違いがないことを確認してたので多分あっている。

int f(int x) { return x*x; } //change here

int lowerbound(int l, int h, int v) {
  while (l < h) {
    int m = (l+h)/2;
    if (v <= f(m)) h = m;
    else l = m+1;
  }
  return l;
}

int upperbound(int l, int h, int v) {
  while (l < h) {
    int m = (l+h)/2;
    if (v < f(m)) h = m;
    else l = m+1;
  }
  return l;
}

STL風に[l,h)区間でf(x)がvとなるようなxの値を返す関数を書いた。ちなみにSTLと区別するために間のアンダーバーは抜いておいた。
lowerboundとupperboundの違いは、if文内の比較演算子を"<="にするか"<"にするかだけで変えられる。これは"="だった場合に低いほうの値lを変えるべきか高いほうの値hを変えるべきかを考えればわかる。


ちなみに[l,h]の区間でコーディングして、"h = m-1"といったようなことをすると挙動がひどいことになった。二分探索を書くときは[l,h)の区間で書いといくのが無難だ。


とりあえず、普通に二分探索を書けといわれたらlowerboundのほうを書けばいいようだ。