lower_bound、upper_boundの基本的な使い方

どちらも二分探索を行う関数で、関数呼び出し時に探索したい値を指定する。

lower_bound

探索したい値以上が現れる最初の位置のイテレータを取得。
インデックスを取得したい場合は、取得したイテレータ - 探索したい領域の先頭すればよい。

例）
探索したい領域 : vector<int> v = {1, 2, 3, 4, 5}
探索したい値 : 3
結果 : 探索したい値以上なので、3の位置のイテレータが取得される。

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

int main(){
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = lower_bound(v.begin(), v.end(), 3);

    int index = it - v.begin();

    // output
    //   index: 2
    //   value: 3
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;
}

探索したい値が見つからなかった場合。領域の最後のイテレータが返される（？）

    vector<int> v = {1, 2, 3, 4, 5};
    auto it = lower_bound(v.begin(), v.end(), 7);

    int index = it - v.begin();

    // output
    //   index: 5
    //   value: 0
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;

upper_bound

探索したい値より大きい値が現れる最初の位置のイテレータを取得。

例）
探索したい領域 : vector<int> v = {1, 2, 3, 4, 5}
探索したい値 : 3

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

int main(){
    vector<int> v = {1, 2, 3, 4, 5};
    auto it = upper_bound(v.begin(), v.end(), 3);

    int index = it - v.begin();

    // output
    //   index: 3
    //   value: 4
    cout << "index: " << index << endl;
    cout << "value: " << v[index] << endl;
    return 0;
}

探索したい値より大きい値なので、4の位置のイテレータが取得される。