二分探索

二分探索 (Binary Search)

概要

単調性のある配列に対して、何らかの値を求めるのを $O(\log{N})$ でできる探索方法。
中央値を用いて、対象値の index があり得る区間を半分に絞り込めることを用いている。

ざっくり計算量解析

中央値を見る。区間を半分にする。

$x$ 回の探索を行うとする。最初の区間長は $N$ 、次は $\frac{N}{2}$ 、...、で、最終的に 1 つに定まる = 長さは 1 になってほしい
つまり、 $N \left( \frac{1}{2} \right)^x = 1 \rightarrow x = \log_2 N = O(\log N)$

注意点

半開区間の考えを使うのがだいじ。無限ループした。
つまり、 $\left[ l, r \right)$ あるいは $\left( l, r \right]$ にしておく

テンプレ

bool solve(ll mid) { return true || false; }

int main() {
  ll ok = 0, ng = 1;

  while (abs(ok - ng) > 1) {
    ll mid = (ok + ng) / 2;
    (solve(mid) ? ok : mid) = mid;
  }
}

lower_bound / upper_bound

組み込みで二分探索をしてくれる関数 lower_bound / upper_bound とか、 binary_search とかもある。自分で書かなくていい。べんり。

lower / upper の違い

lower_bound(a.begin(), a.end(), x) : 配列 $a$ に対して、$a_i \ge x$ となる最初のイテレータを返す
upper_bound(a.begin(), a.end(), x) : 配列 $a$ に対して、$a_i > x$ となる最初のイテレータを返す

ざっくりといえば、イテレータ範囲内に $x$ を含めるか含めないかみたいな

$x$ がいくつあるかの判定

例えば multiset とか count 配列 とか使ってもいいけど、制約によっては遅いこともある...

lower / upper_bound を使うと高速。
やってることはちょっと考えれば明らか？

auto itr1 = lower_bound(a.begin(), a.end(), x);
auto itr2 = upper_bound(a.begin(), a.end(), x);
int cnt = itr2 - itr1;

注意点

set とか map とか、ランダムアクセスイテレータじゃないものは遅い。
lower_bound(set.begin(), set.end(), x) のかわりに set.lower_bound(x) を使うといいかんじ。