C++で非増加順（降順）ソートされたvectorの下限と上限を求める方法

本記事では、C++ STLにおいて非増加順（降順）にソートされた配列に対して、vector::lower_bound()およびvector::upper_bound()を使用する方法について詳しく解説します。

vectorとは

vectorは動的配列に近い性質を持つコンテナです。要素の挿入や削除を行うと、必要に応じて自身のサイズを自動的に拡張・縮小できるため、要素数が事前に確定していない場合でも柔軟にデータを管理できます。

lower_boundとupper_boundの動作

降順にソートされたvectorに対しては、次のようなイテレータが返されます。

• lower_bound()：指定した値「以下」の要素が最初に現れる位置を指すイテレータを返します。
• upper_bound()：指定した値「未満」の要素が最初に現れる位置を指すイテレータを返します。

入力例

30 30 30 20 20 20 10 10

出力例

20のlower_bound = 3
20のupper_bound = 6

入力例

9 9 8 8 8 7 7 7 6 6 6 6

出力例

7のlower_bound = 5
7のupper_bound = 8

戻り値

lower_bound()は同値範囲の先頭要素を指すイテレータを返し、upper_bound()は同値範囲の末尾要素の次の位置を指すイテレータを返します。つまり、両者の間には「指定した値と等しいすべての要素」が含まれることになります。

実装の手順

• まずvectorを初期化します。
• vectorの要素をgreater<int>()を使って降順（非増加順）にソートします。
• lower_bound()で下限を求めます。
• upper_bound()で上限を求めます。
• 最後に両方の結果を出力します。

重要なポイント： 降順にソートされたvectorに対してlower_bound()/upper_bound()を正しく動作させるには、第4引数として比較関数オブジェクトgreater<int>()を渡す必要があります。これを省略すると誤った結果になります。また、ソートされていないvectorに対してこれらの関数を使用することはできません。

サンプルコード1

// lower_boundとupper_boundの動作を示すC++プログラム
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int vect[] = {13, 13, 13, 16, 16, 16, 17, 17, 17, 17, 18, 18};
    vector<int> v(vect, vect + 12);

    // 降順にソート
    sort(v.begin(), v.end(), greater<int>());

    cout << "\nSorted Vector: ";
    for (auto i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    cout << "\n";

    vector<int>::iterator low, up;
    low = lower_bound(v.begin(), v.end(), 17, greater<int>());
    up = upper_bound(v.begin(), v.end(), 17, greater<int>());

    cout << "Lower bound = " << (low - v.begin()) << "\n";
    cout << "Upper bound = " << (up - v.begin()) << "\n";
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Sorted Vector: 18 18 17 17 17 17 16 16 16 13 13 13
Lower bound = 2
Upper bound = 6

サンプルコード2

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

int main() {
    int vect[] = {5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10};
    vector<int> v(vect, vect + 16);

    // 降順にソート
    sort(v.begin(), v.end(), greater<int>());

    cout << "\nSorted Vector: ";
    for (auto i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
    cout << "\n";

    vector<int>::iterator low, up;
    low = lower_bound(v.begin(), v.end(), 8, greater<int>());
    up = upper_bound(v.begin(), v.end(), 8, greater<int>());

    cout << "Lower bound = " << (low - v.begin()) << "\n";
    cout << "Upper bound = " << (up - v.begin()) << "\n";
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Sorted Vector: 10 10 9 9 9 8 8 8 8 7 7 7 5 5 5 5
Lower bound = 5
Upper bound = 9

まとめ

降順ソートされたvectorから特定の値の範囲を取得する場合は、sort()・lower_bound()・upper_bound()のすべてにgreater<int>()を渡すことが重要です。これにより二分探索が正しく機能し、同値要素の開始位置と終了位置をO(log n)の計算量で効率的に求められます。