二分探索をやってみよう！

昨日PKUにて、解き方の方針は立ったがどうしようか・・という場面に遭遇した。

簡単にいうとこんな感じ。

1 - 50,000までの数の中で、ある条件を満たす数の最大値はいくらか？？数が小さければ小さいほど条件を余裕をもって満たせることは明らか。。

じゃー、1-50,000までインクリメントしてやってみるか。。。

いや、待て。そんなんじゃ時間足りない気がする。条件を満たすかどうか調べるの結構時間使いそうだし。じゃあどうしよう・・・

そこで閃いた。

①まず、25,000で試してみよう。

②25,000で条件を満たすのなら、今度は25,000 - 50,000までの探索をしよう。満たさないなら0-25,000まで探索しよう。

①②の操作で探索範囲が1/2になった。同じことを逐次10回やれば探索範囲は大体1/1000くらいになるな。20回やれば1/1,000,000くらいにできるな。。

単純にインクリメントした場合は、最悪50,000個の数を調べないといけないけど、この範囲を1/2に狭めていく方法を使えば、最悪でも16回以下くらいで探索ができるな！！

ん・・何かこれ、もしかしてBinary Searchとか言うやつじゃないのか。

ググってみると、ありました。Binary Search(二分探索)。そうそうこれこれ。。

早速ちょっと試しに簡単な例題を作って練習してみました。

例題

単調増加関数fがある。ある自然数nが与えられた時、f(x) > nとなる最小の自然数xを求めなさい。

ここで、f(x) = (int)log(x) + (int)sqrt(x) + 1とする。

単純な線形探索とBinary Searchで実行速度を比べてみよう。

ソースはこんな感じ。

view plainprint?

1. using namespace std;  
2.   
3. int func(int n) {  
4.   
5.     return (int) log(n) + (int)sqrt(n) +  1;  
6. }  
7.   
8. int main() {  
9.     int target = 7777;  
10.     int i = 0;  
11.   
12.     // Linear Search  
13.     while (1) {  
14.         if (func(i) > target)  
15.             break;  
16.         i++;  
17.     }  
18.     cout << i << endl;  
19.   
20.     // Binary Search  
21.     int left = 0;  
22.     int right = INT_MAX;  
23.     i = left + (right - left) / 2;  
24.     while (1) {  
25.         if (func(i) > target && func(i - 1) <= target)  
26.             break;  
27.   
28.         if (func(i) > target)  
29.             right = i;  
30.         else  
31.             left = i;  
32.         i = left + (right - left) / 2;  
33.     }  
34.     cout << i << endl;  
35. }  

using namespace std;

int func(int n) {

    return (int) log(n) + (int)sqrt(n) +  1;
}

int main() {
    int target = 7777;
    int i = 0;

    // Linear Search
    while (1) {
        if (func(i) > target)
            break;
        i++;
    }
    cout << i << endl;

    // Binary Search
    int left = 0;
    int right = INT_MAX;
    i = left + (right - left) / 2;
    while (1) {
        if (func(i) > target && func(i - 1) <= target)
            break;

        if (func(i) > target)
            right = i;
        else
            left = i;
        i = left + (right - left) / 2;
    }
    cout << i << endl;
}

ちなみに x= 60,217,600だが、探索にかかった時間は
Linear Searchの場合は、12.347秒。Binary Searchの場合は、0.000000011秒（笑）。

全然違います。

他にもBSはいろいろな使い道がありそうです。

DPと並んでアルゴリズムコンテストでは必須アイテムの一つと言えるでしょう。

ちなみにこれが昨日遭遇したBinary Searchを使って解くPKUの問題。興味のある人はチャレンジしてみて下さい！僕も実装はまだです。。。