第55回 探索系アルゴリズム ★目玉
配列の中から要素を見つける一連の関数：find / find_if / binary_search / lower_bound / upper_bound / equal_range。ソート済みかで使い分けます。
このページで押さえること
✅ 最低限
std::find ― 線形探索（ソート不要）std::find_if ― 述語で探すstd::binary_search ― ソート済み前提・二分探索std::lower_bound ― 挿入位置を返す
⭐ 余裕があれば
upper_bound / equal_range- 計算量の違い
- std::find_if_not / adjacent_find
- std::search（部分列探索）
1. 一覧
| 関数 | ソート要件 | 戻り値 | 計算量 |
|---|
std::find | 不要 | 見つかったイテレータ / end() | O(n) |
std::find_if | 不要 | 述語を満たす最初のイテレータ | O(n) |
std::count | 不要 | 一致する要素数 | O(n) |
std::binary_search | 必須 | bool（存在するか） | O(log n) |
std::lower_bound | 必須 | value 以上の最初のイテレータ | O(log n) |
std::upper_bound | 必須 | value より大の最初のイテレータ | O(log n) |
std::equal_range | 必須 | value と一致する範囲の pair | O(log n) |
2. 線形探索系 ― find / find_if / count
find_if述語
std::vector<int> v = {3, 1, 4, 1, 5, 9};
// 特定の値を探す
auto it = std::find(v.begin(), v.end(), 5);
if (it != v.end()) { /* 見つかった */ }
// 条件で探す
auto it2 = std::find_if(v.begin(), v.end(),
[](int x){ return x > 4; });
// 個数を数える
auto cnt = std::count(v.begin(), v.end(), 1); // 1 が何個か: 2
auto cnt2 = std::count_if(v.begin(), v.end(),
[](int x){ return x > 3; }); // 条件を満たす個数
3. 二分探索系 ― ソート済み前提
binary_search / lower_boundO(log n)
std::vector<int> v = {1, 3, 3, 5, 7, 9}; // ソート済み
std::binary_search(v.begin(), v.end(), 5); // true
// lower_bound: value 以上の最初の位置
auto lb = std::lower_bound(v.begin(), v.end(), 3);
// v[1] を指す（最初の 3）
// upper_bound: value より大の最初の位置
auto ub = std::upper_bound(v.begin(), v.end(), 3);
// v[3] を指す（5 の位置）
// equal_range: [lower, upper) の範囲
auto [a, b] = std::equal_range(v.begin(), v.end(), 3);
// 3 が出現する範囲
使い分け：
- 「存在するか」だけ →
binary_search
- 「挿入位置」を知りたい →
lower_bound
- 「値の個数」を知りたい →
upper_bound - lower_bound
4. パフォーマンス比較
▶ 線形 vs 二分探索
v = ソート済みの 1000000 要素の場合：
std::find: 平均 500,000 回比較（O(n)）std::binary_search: 最大 20 回比較（O(log n) = log₂(10⁶) ≈ 20）
explicit: 25,000 倍の差
線形探索: ~500,000 比較
二分探索: ~20 比較
確認クイズ
Q1. 未ソートの vector から要素を探すときに適切なのは？
std::binary_search
std::find
std::lower_bound
std::equal_range
二分探索系はソート済み前提。未ソートなら線形の find / find_if を使う。
Q2. ソート済み vector で「値 3 を 5 に置き換えるべき位置」を知るには？
std::find(v.begin(), v.end(), 3)
std::lower_bound(v.begin(), v.end(), 3)
std::count
std::sort
lower_bound はソート済み配列から「value 以上になる最初の位置」を O(log n) で返します。
Q3. std::find が見つからなかったときの戻り値は？
-1
nullptr
v.end()
v.begin()
STL 全体で「見つからない」は end() を返す慣例。if (it != v.end()) でチェック。
Q4. ソート済み 100 万要素から二分探索する比較回数の最大は？
1,000,000
1,000
約 20（log₂(10⁶) ≈ 20）
100
二分探索は O(log₂ n)。10⁶ なら約 20 回。線形探索の 500,000 回と圧倒的な差。