C++でソート済みのpair型vectorに対して二分探索を行う方法

C++では、std::pair を格納したソート済みの std::vector に対しても、標準ライブラリの binary_search 関数を使って二分探索（バイナリサーチ）を実行できます。ただし、pair のどの要素（first / second）をキーとして比較するかをコンパイラに伝える必要があるため、カスタム比較ファンクタを定義するのがポイントです。

アルゴリズム

処理の流れは以下の通りです。

開始
　　keycompare 構造体を宣言する
　　　　operator()(const pair& v, const int& k) を定義し、bool を返す
　　　　　　status = v.first < k
　　　　　　status を返す
　　　　operator()(const int& k, const pair& v) を定義し、bool を返す
　　　　　　status = k < v.first
　　　　　　status を返す
　　vector v を宣言する
　　v 内に int 型のキーと値のペアを宣言する
　　push_back() 関数で v に値を挿入する
　　sort() 関数で v の全要素をソートする
　　「Sorted vector」を出力する
　　「KEY」「VALUE」を出力する
　　for ループで各要素 n の first と second を出力する
　　binary_search(v.begin(), v.end(), 50, keycompare()) が真なら
　　　　「50 exists in vector」を出力する
　　偽なら
　　　　「50 does not exist」を出力する
　　binary_search(v.begin(), v.end(), 7, keycompare()) が真なら
　　　　「7 exists in vector」を出力する
　　偽なら
　　　　「7 does not exist」を出力する
終了

ポイント：比較ファンクタ keycompare の役割

binary_search は通常 < 演算子で要素同士を比較しますが、pair 型の vector に対して単純な整数値を渡すと型が一致せず、そのままでは使えません。そこで keycompare 構造体のように、operator() を「(pair, 整数)」と「(整数, pair)」の2パターンでオーバーロードしたファンクタを第4引数として渡すことで、pair の first 要素（キー）を基準とした双方向の比較が可能になります。

サンプルコード

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

struct keycompare {
    bool operator()(const pair<int, int>& v, const int& k) {
        return (v.first < k);
    }
    bool operator()(const int& k, const pair<int, int>& v) {
        return (k < v.first);
    }
};

int main() {
    vector<pair<int, int>> v;
    v.push_back(make_pair(7, 26));
    v.push_back(make_pair(6, 76));
    v.push_back(make_pair(4, 16));
    v.push_back(make_pair(5, 36));

    // ベクトルをキー順にソート
    sort(v.begin(), v.end());

    cout << "Sorted vector" << endl;
    cout << "KEY" << '\t' << "VALUE" << endl;
    for (auto& n : v)
        cout << n.first << '\t' << n.second << endl;

    if (binary_search(v.begin(), v.end(), 50, keycompare()))
        cout << "50 exists in vector";
    else
        cout << "50 does not exist";
    cout << endl;

    if (binary_search(v.begin(), v.end(), 7, keycompare()))
        cout << "7 exists in vector";
    else
        cout << "7 does not exist";

    return 0;
}

実行結果

Sorted vector
KEY     VALUE
4       16
5       36
6       76
7       26
50 does not exist
7 exists in vector

まとめ

pair 型の vector に対して二分探索を行う場合は、キーとなる要素（本例では first）に基づいて双方向の比較ができるファンクタを用意することが重要です。二分探索の計算量は O(log n) であり、先頭から順に調べる線形探索 O(n) と比べて、大量のデータでも高速に要素の存在を判定できます。