Tags:cplibrarysearch

二分探索 (Binary Search)

概要

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

ざっくり計算量解析

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

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

注意点

半開区間の考えを使うのがだいじ。無限ループした。
つまり、 [l,r)\left[ l, r \right) あるいは (l,r]\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) : 配列 aa に対して、aixa_i \ge x となる最初のイテレータを返す
upper_bound(a.begin(), a.end(), x) : 配列 aa に対して、ai>xa_i > x となる最初のイテレータを返す

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

xx がいくつあるかの判定

例えば 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) を使うといいかんじ。