C++

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 = lower_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の位置のイテレータが取得される。