lower_bound / upper_bound

1. lower_bound

• 이진 탐색 기법이다.
• 배열이 정렬되어 있어야 한다.
• 찾으려는 key값이 없으면 key값보다 이상인 가장 작은 정수 값을 찾는다.

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	vector<int> v = {1, 2, 3, 3, 4, 4, 5, 5};
	
	cout << "lower_bound(2) : " << lower_bound(v.begin(), v.end(), 2) - v.begin() << '\n';
	cout << "lower_bound(4) : " << lower_bound(v.begin(), v.end(), 4) - v.begin() << '\n';
	cout << "lower_bound(5) : " << lower_bound(v.begin(), v.end(), 5) - v.begin() << '\n';
	
	return 0;
}

 

lower_bound는 key값보다 큰 수 중에서 가장 작은 수의 iterator를 반환한다.

따라서 그냥 출력하면 위치를 알 수 없고, 벡터일 경우는 begin() iterator를 빼주어야 해당하는 인덱스를 구할 수 있다.

만약 배열일 경우 배열의 이름을 빼주면 된다.

 

 

2. upper_bound

• 이진 탐색 기법이다.
• 배열이 정렬되어 있어야 한다.
• key값을 초과하는 가장 첫 번째 원소의 위치를 구한다.

 

lower_bound와 사용법은 같다.

아래는 lower_bound와 똑같은 예시이다.

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	vector<int> v = {1, 2, 3, 3, 4, 4, 5, 5};
	
	cout << "upper_bound(2) : " << upper_bound(v.begin(), v.end(), 2) - v.begin() << '\n';
	cout << "upper_bound(4) : " << upper_bound(v.begin(), v.end(), 4) - v.begin() << '\n';
	cout << "upper_bound(5) : " << upper_bound(v.begin(), v.end(), 5) - v.begin() << '\n';
	
	return 0;
}

 

 

벡터에 5보다 큰 수는 없으므로 벡터의 마지막 원소 다음의 iterator, 즉 end() iterator를 반환한다.