[C++] upper_bound()の使い方 – ニ分探索/lower_boundとの違い

upper_bound()は、ソートされた範囲で指定した値より「大きい」最初の要素の位置を返すC++標準ライブラリの関数です。

一方、lower_bound()は指定した値「以上」の最初の要素の位置を返します。

両者とも二分探索を用いており、計算量は\(O(\log n)\)です。

違いとして、upper_bound()は範囲内で指定値と等しい要素をスキップし、その次の位置を返すのに対し、lower_bound()は等しい要素を含む位置を返します。

upper_bound()の使い方

upper_bound()は、C++の標準ライブラリに含まれるアルゴリズムで、ソートされた範囲内で特定の値より大きい最初の要素の位置を返します。

この関数は、二分探索を利用して効率的に検索を行います。

以下に、upper_bound()の基本的な使い方を示します。

基本的な使い方

まず、upper_bound()を使用するためには、<algorithm>ヘッダーをインクルードする必要があります。

次に、ソートされた配列やベクターを用意し、検索したい値を指定します。

#include <iostream>
#include <vector>
#include <algorithm> // upper_boundを使用するために必要
int main() {
    std::vector<int> numbers = {1, 2, 4, 4, 5, 6}; // ソートされた配列
    int value = 4; // 検索したい値
    // upper_boundを使用して、4より大きい最初の要素の位置を取得
    auto it = std::upper_bound(numbers.begin(), numbers.end(), value);
    // 結果を出力
    if (it != numbers.end()) {
        std::cout << "4より大きい最初の要素は: " << *it << std::endl;
    } else {
        std::cout << "4より大きい要素は存在しません。" << std::endl;
    }
    return 0;
}

4より大きい最初の要素は: 5

使い方のポイント

• upper_bound()は、ソートされた範囲でのみ正しく動作します。
• 戻り値はイテレータで、指定した値より大きい最初の要素の位置を指します。
• 値が範囲内に存在しない場合、end()イテレータが返されます。

このように、upper_bound()を使うことで、特定の値より大きい要素を効率的に見つけることができます。

次に、lower_bound()との違いについて見ていきましょう。

lower_bound()との違い

lower_bound()とupper_bound()は、どちらもC++の標準ライブラリに含まれるアルゴリズムで、ソートされた範囲内での検索を行いますが、返す値の条件が異なります。

以下に、両者の違いを詳しく説明します。

機能の違い

以下に、lower_bound()とupper_bound()の使い方を示すサンプルコードを示します。

#include <iostream>
#include <vector>
#include <algorithm> // lower_boundとupper_boundを使用するために必要
int main() {
    std::vector<int> numbers = {1, 2, 4, 4, 5, 6}; // ソートされた配列
    int value = 4; // 検索したい値
    // lower_boundを使用して、4以上の最初の要素の位置を取得
    auto lowerIt = std::lower_bound(numbers.begin(), numbers.end(), value);
    // upper_boundを使用して、4より大きい最初の要素の位置を取得
    auto upperIt = std::upper_bound(numbers.begin(), numbers.end(), value);
    // 結果を出力
    std::cout << "4以上の最初の要素は: " << (lowerIt != numbers.end() ? *lowerIt : -1) << std::endl;
    std::cout << "4より大きい最初の要素は: " << (upperIt != numbers.end() ? *upperIt : -1) << std::endl;
    return 0;
}

4以上の最初の要素は: 4
4より大きい最初の要素は: 5

使い分けのポイント

• lower_bound()は、指定した値が存在する場合、その位置を返します。

値が存在しない場合は、次に大きい要素の位置を返します。

• upper_bound()は、指定した値より大きい要素の位置を返すため、同じ値が複数存在する場合、最初の要素の次の位置を返します。
• どちらの関数も、ソートされた範囲でのみ使用することが重要です。

このように、lower_bound()とupper_bound()は似たような機能を持ちながらも、異なる条件で要素を検索するため、用途に応じて使い分けることが大切です。

次に、これらの関数を組み合わせた応用例について見ていきましょう。

upper_bound()とlower_bound()を組み合わせた応用例

upper_bound()とlower_bound()を組み合わせることで、特定の範囲内にある要素の数を効率的にカウントすることができます。

これにより、特定の値の出現回数や、範囲内の要素を簡単に取得することが可能です。

以下に、具体的な応用例を示します。

例: 特定の範囲内の要素数をカウントする

以下のサンプルコードでは、指定した範囲内にある要素の数をカウントします。

#include <iostream>
#include <vector>
#include <algorithm> // lower_boundとupper_boundを使用するために必要
int main() {
    std::vector<int> numbers = {1, 2, 4, 4, 5, 6}; // ソートされた配列
    int lowerValue = 4; // 範囲の下限
    int upperValue = 5; // 範囲の上限
    // lower_boundを使用して、4以上の最初の要素の位置を取得
    auto lowerIt = std::lower_bound(numbers.begin(), numbers.end(), lowerValue);
    // upper_boundを使用して、5より大きい最初の要素の位置を取得
    auto upperIt = std::upper_bound(numbers.begin(), numbers.end(), upperValue);
    // 範囲内の要素数を計算
    int count = upperIt - lowerIt;
    // 結果を出力
    std::cout << lowerValue << "以上" << "かつ" << upperValue << "以下の要素数は: " << count << std::endl;
    return 0;
}

4以上かつ5以下の要素数は: 3

• lower_bound()を使用して、指定した下限(この例では4)以上の最初の要素の位置を取得します。
• upper_bound()を使用して、指定した上限(この例では5)より大きい最初の要素の位置を取得します。
• これらのイテレータの差を取ることで、指定した範囲内にある要素の数を簡単に計算できます。

応用シナリオ

• データ分析: 大量のデータから特定の範囲にあるデータポイントを迅速にカウントする際に役立ちます。
• ゲーム開発: プレイヤーのスコアやレベルを特定の範囲でフィルタリングする場合に使用できます。
• 統計処理: 特定の条件を満たすデータの集計や分析に利用できます。

このように、upper_bound()とlower_bound()を組み合わせることで、さまざまな場面で効率的なデータ処理が可能になります。

まとめ

この記事では、C++のupper_bound()とlower_bound()の使い方や、それぞれの違い、さらには両者を組み合わせた応用例について詳しく解説しました。

これらの関数を活用することで、ソートされたデータから特定の条件に合った要素を効率的に検索し、範囲内の要素数を簡単にカウントすることが可能です。

ぜひ、実際のプログラムにこれらの関数を取り入れて、データ処理の効率を向上させてみてください。