C++のlower_bound()関数とは？使い方をサンプルコード付きで解説

はじめに

このチュートリアルでは、C++における lower_bound() 関数について詳しく解説します。

lower_bound() は、C++の標準ライブラリ（<algorithm> ヘッダー）に含まれる関数の一つで、ソート済みコンテナの中から「指定した値以上となる最初の要素」へのイテレータを返します。二分探索を用いて実装されているため、要素数が多い場合でも高速に動作するのが特徴です。

lower_bound() の基本仕様

• 検索対象の範囲は事前にソートされている必要があります
• 指定した値以上の要素が見つかった場合、その位置へのイテレータを返します
• すべての要素が指定値より小さい場合は、範囲の末尾（end()）を返します

サンプルコード

以下は、std::vector に対して lower_bound() を使用する具体例です。

#include <bits/stdc++.h>
int main(){
    std::vector<int> v{ 10, 20, 30, 40, 50 };
    std::cout << "Vector contains :";
    for (unsigned int i = 0; i < v.size(); i++)
        std::cout << " " << v[i];
    std::cout << "\n";
    std::vector <int>::iterator low1, low2;
    low1 = std::lower_bound(v.begin(), v.end(), 35);
    low2 = std::lower_bound(v.begin(), v.end(), 55);
    std::cout
        << "\nlower_bound for element 35 at position : "
        << (low1 - v.begin());
    std::cout
        << "\nlower_bound for element 55 at position : "
        << (low2 - v.begin());
    return 0;
}

実行結果

Vector contains : 10 20 30 40 50
lower_bound for element 35 at position : 3
lower_bound for element 55 at position : 5

実行結果の解説

ケース1：値 35 を検索した場合
ベクターには 35 という要素は存在しませんが、35 以上となる最初の要素は位置 3 の「40」です。そのため、lower_bound() は位置 3 を返します。

ケース2：値 55 を検索した場合
ベクター内のすべての要素（最大値 50）が 55 より小さいため、該当する要素は存在しません。この場合、lower_bound() は範囲の末尾、すなわち位置 5（end() に相当）を返します。

まとめ

lower_bound() は、ソート済みデータから条件に合う要素を効率的に探したいときに非常に便利な関数です。類似の関数として「指定値より大きい最初の要素」を返す upper_bound() もあります。両者を使い分けることで、範囲検索などの処理も簡潔に記述できます。