二分探索 (Binary Search)
概要
単調性のある配列に対して、何らかの値を求めるのを でできる探索方法。
中央値を用いて、対象値の index があり得る区間を半分に絞り込めることを用いている。
ざっくり計算量解析
中央値を見る。区間を半分にする。
回の探索を行うとする。最初の区間長は 、次は 、...、で、最終的に 1 つに定まる = 長さは 1 になってほしい
つまり、
注意点
半開区間の考えを使うのがだいじ。無限ループした。
つまり、 あるいは にしておく
テンプレ
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)
: 配列 に対して、 となる最初のイテレータを返す
upper_bound(a.begin(), a.end(), 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)
を使うといいかんじ。