C++で2分探索


このエントリーをはてなブックマークに追加

入力として与えられた整数がある値以上のときはtrue, そうでないときはfalseを返すブラックボックスな関数bool Check(int n)があるとする。その「ある値」を求めるコードが以下。

#include <iostream>

using namespace std;

bool Check(int num){
    return (num >= 7777) ? true : false;
}

int main(){

    // 探索範囲は[lo, hi]
    int lo = 1;
    int hi = 100000;

    while(lo < hi) {
        // printf("lo, hi = %d, %d\n", lo, hi);
        int k = (lo + hi) / 2;
        if (Check(k))
            hi = k;
        else
            lo = k + 1;
    }

    cout << lo << endl;    
    return 0;
}

出力は

7777

となる。
ideoneに貼りつけたコードはこちら