C++ lower_bound関数：イテレータで二分探索【徹底解説】

1年 ago
夏樹, 風
1 minute

C++のlower_bound関数は、ソートされた範囲で、指定された値以上の最初の要素の位置を返すために使用されます。

以下はlower_bound関数の構文です：

std::vector<int>::iterator lower_bound (std::vector<int>::iterator first, std::vector<int>::iterator last, const int& val);

lower_bound 関数を使用する際は、まず、区間が昇順に並べ替えられていることを確認する必要があります。その後、関数には、区間の開始位置を指すイテレーター first、区間の末尾位置を指すイテレーター last、および検索する値 val の3つの引数を渡す必要があります。

指定された範囲内で、与えられた値val以上の最初の要素を検索し、その要素を指すイテレータを返すlower_bound関数。条件に合致する要素が見つからない場合は、範囲の末尾を指すイテレータlastを返す。

以下は、lower_bound関数を使用する方法を示す簡単なサンプルコードです。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 查找不小于 5 的第一个元素的位置
    std::vector<int>::iterator it = std::lower_bound(vec.begin(), vec.end(), 5);

    if (it != vec.end()) {
        std::cout << "第一个不小于5的元素位置为：" << std::distance(vec.begin(), it) << std::endl;
    } else {
        std::cout << "未找到符合条件的元素" << std::endl;
    }

    return 0;
}

上記の例では、lower_bound 関数はvec内で5以上の最初の要素を探し出します。vecは既に昇順に並べ替えられているため、返されるイテレータは5を指します。

bannerAds