Algoogle

Algorithm for Programming Contest

Binary Search

基本情報


計算量

N := 区間の幅

解説


ある区間の値xに対して判定関数ok(x)が返す値が単調であるときに, その境界を効率よく見つけるアルゴリズム.
単調であるというのは, 判定関数ok()がtrueならo, falseならxとすると例えば区間[0,9]で

1
2
3

    0 1 2 3 4 5 6 7 8 9
    x x x x x x x o o o

みたいになっているということ.

ok()がtrueになる最小の値uを求めたいとする.
下限と上限をそれぞれlb, ub(lower bound, upper bound)とし, その中間の値をmidとすると
ok(mid)がtrueなら, uはmid以下なのでub=midとする.
ok(mid)がfalseなら, uはmidより多きいのでlb=midとする.
これをlbとubが隣り合うまで繰り返せば, 最終的にubがuになっている.
これは毎ステップ探索する区間が半分になっているので, 最初の区間の幅をNとするとlog N回程度の計算で求まることがわかる.

この方法で2分探索をするときは, ubには常にtrueなるような値が入り, lbにfalseになるような値が入ると考えるとよい.
区間の取り方や求めたい値の条件(条件を満たす最大や条件を満たす最小など)によって細かい部分が変わるが, これを意識すれば間違えることは少ない.
例えばここまで単調非減少になっているものを考えてきたが, 単調非増加になっている場合も同じように考えればよいことがわかる.
つまりlbにtrueになるような値が入り, ubにはfalseになるような値が常に入ってくる.

また離散的ではない場合はこのやり方では隣り合うという判定が難しいので値が収束するのに十分な固定回数分(大体50回もやれば十分)だけ繰り返す.

コードは判定関数が単調非減少なときのもの

コード


(binary-search.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binary_search(int l, int r) {
    int lb = l, ub = r, mid;
    while(ub-lb>1) {
        mid = (lb+ub)/2;
        if(ok(mid)) ub = mid;
        else lb = mid;
    }
    return ub;
}

double binary_search(double l, double r) {
    double lb = l, ub = r, mid;
    int cnt = 100;
    while(cnt--) {
        mid = (lb+ub)/2;
        if(ok(mid)) ub = mid;
        else lb = mid;
    }
    return ub;
}

問題


Comments