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