lower_boundとupper_boundとbinary_search

もう毎回忘れてほとんど使えないのでメモ

• lower_boundはvalue以上で最初のiteratorを返す
• upper_boundはvalueより大きい最初のiteratorを返す
• binary_searchはvalueがあるかどうかを返す;

どれもソート済みに使ってね。

最後に比較関数を入れたsampleを貼っておこう

typedef pair<int, int> P;

int main()
{
    vector<int> A{3,6,7,9,10,19,31};
    cout << distance(A.begin(), lower_bound(A.begin(), A.end(), 9)) << endl;
    cout << distance(A.begin(), upper_bound(A.begin(), A.end(), 9)) << endl;

    vector<P> B{{2,4}, {5,3}, {5,7}, {6,1}};
    auto it = upper_bound(B.begin(), B.end(), P(5, 0), [](const P& l, const P& r)->bool{return l.first < r.first;});
    cout << it->first << " " << it->second << endl;
}