std::set や std::map などでよく登場する lower_bound と upper_bound。
この記事では、これらの関数の意味・違い・使い方、さらに競技プログラミングでの応用例までわかりやすく解説します。

✅ 結論：`lower_bound` と `upper_bound` の違い

関数名	意味	条件	返すイテレータ
`lower_bound(x)`	x以上の要素	`>= x`	最初の該当要素
`upper_bound(x)`	xより大きい要素	`> x`	最初の該当要素

🔰 基本使用例（`std::set`）

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> S = {10, 20, 30, 40, 50};

    auto it1 = S.lower_bound(25); // -> 30
    auto it2 = S.upper_bound(30); // -> 40

    if (it1 != S.end()) cout << "lower_bound(25): " << *it1 << endl;
    if (it2 != S.end()) cout << "upper_bound(30): " << *it2 << endl;
    return 0;
}

✅ 出力

lower_bound(25): 30
upper_bound(30): 40

🧪 動作まとめ表

set<int> S = {10, 20, 30, 40, 50} の場合：

検索値 x	`lower_bound(x)`	`upper_bound(x)`
10	10	20
25	30	30
30	30	40
50	50	end()
60	end()	end()

🔄 std::vector との違い

vector の場合、lower_bound / upper_bound はalgorithmにある関数を使います。

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

int main() {
    vector<int> V = {10, 20, 30, 40, 50};

    auto it = lower_bound(V.begin(), V.end(), 25); // 30 の位置

    if (it != V.end())
        cout << *it << endl;  // 30
}

✅ 注意点：
vector はソートされている必要があります。

戻り値はイテレータなので、位置を知りたい場合は it - V.begin() で添字が得られます。

📌 競技プログラミングでの実用テクニック

🔁 `x以下の最大値` を探す方法

std::set は降順ソートができないので、次のように負数を使って工夫します：

set<long long> S_neg;
S_neg.insert(-x); // 負の値を挿入（逆向き管理）

// x以下の最大の値を取得するには：
long long max_le_x = -(*S_neg.lower_bound(-x));

これにより、x以下の最大の値が O(log N) で求められます。

🧠 よくある使い分け

目的	使用関数	説明
x以上の最小値	lower_bound(x)	範囲の開始・検索
xより大きい最小値	upper_bound(x)	範囲の終了・次の要素
x以下の最大値	lower_bound(x+1) のイメージ	降順管理や負数で工夫

🔚 まとめ

・lower_bound は「x以上」の最小値を返す

・upper_bound は「xより大きい」の最小値を返す

・x以下の最大値を求める場合は、負の値を使うテクニックが有効

・std::set, std::map と組み合わせて、O(log N) で高速に探索できる

📘 おすすめ学習リソース

cpprefjp - lower_bound
AtCoder典型90問やABCコンテストでの練習