13
9

More than 3 years have passed since last update.

# lower_bound、upper_boundの基本的な使い方

Last updated at Posted at 2018-07-22

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

## lower_bound

インデックスを取得したい場合は、`取得したイテレータ - 探索したい領域の先頭`すればよい。

``````#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

``````#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;
}
``````

13
9
0

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
13
9