binary_search関数

http://www.geocities.jp/ky_webid/cpp/library/020.html

既にソート済みのデータを対象に検索等を行うときに便利な関数の話です。

まずはbinary_search関数を見てみます。

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std;

int main () {
    vector<int> data;
    
    // ランダムな値を格納する
    srand( static_cast<unsigned int>( time(NULL) ) );
    for(int i=0;i<10;++i) {
        data.push_back( rand() % 10 );
    }
    
    // 昇順ソートしておく
    sort(data.begin(),data.end());
    
    // 5という値をバイナリサーチする
    if ( binary_search( data.begin(),data.end(), 5 ) ) {
        cout << "見つかりました" << endl;
    }
    else {
        cout << "見つかりませんでした" << endl;
    }
    
    return 0;
}

$ main
見つかりました

$ main
見つかりませんでした

$ main
見つかりませんでした

できました。簡単ですね。

ちなみに元のデータが降順でソートされていた場合、binary_search関数を呼び出す際に降順で検索するという指定をしなければなりません。

// 降順でソート1
sort(data.begin(),data.end(), greater<int>());

// 降順用のバイナリサーチする
binary_search( data.begin(),data.end(), 5, greater<int>() );

注意が必要ですね。