C++ 二分探索(lower_bound, upper_bound)

二分探索とは?

概要

• 配列の探索方法の一つ。
• O(N)かかる線形探索とは異なり、O(logN)の計算量で探索でき効率的。
• 昇順ソートした配列にしか使えない点に注意。
• 参考サイト：競プロ覚書：二分探索，std::lower_bound を使いこなす - pyてよn日記

例題：配列から「9」を探すとき

線形探索の場合

二分探索の場合

C++における二分探索

(1) lower_bound

• 指定したkey以上の最小のイテレータを取得。
• イテレータから配列の何番目かを取り出すためには、std::distanceを使用。
• 例) key = 5の場合は、a[2] = 5のイテレータを返す。

ソースコード

#include <iostream>
#include <vector>

int main() {
    
    //宣言
    std::vector<int> a{ 1, 3, 5, 7, 9, 11, 14};

    //探索
    int key = 5;
    auto ite = std::lower_bound(a.begin(), a.end(), key);
    int index = std::distance(a.begin(), ite);
    std::cout << "key = 5以上を満たす要素は" << index << "番目にある" << std::endl;

    return 0;
}

実行結果

key = 5以上を満たす要素は2番目にある

(2) upper_bound

• 指定したkeyより大きい要素の最小のイテレータを取得。
• lower_boundと異なり、key以上ではないため、keyと等しい要素のイテレータは取得できない。
• lower_boundと同様に、イテレータから配列の何番目かを取り出すためには、std::distanceを使います。
• 例) key = 5の場合は、a[3] = 7のイテレータを返す。

ソースコード

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

int main() {
    
    //宣言
    std::vector<int> a{ 1, 3, 5, 7, 9, 11, 14};

    //探索
    int key = 5;
    auto ite = std::upper_bound(a.begin(), a.end(), key);
    int index = std::distance(a.begin(), ite);
    std::cout << "5より大きい要素の先頭は、a[" << index << "] = " << a[index] << std::endl;

    return 0;
}

実行結果

5より大きい要素の先頭は、a[3] = 7