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コンテストでの練習