[C++] lower_bound()와 upper_bound()

lower_bound()는 정렬되어 있는 배열에서 찾으려는 값의 첫 인덱스,

upper_bound()는 찾으려는 값을 초과하는 인덱스 중 첫 인덱스를 찾는다.

 

이진탐색을 기반으로 탐색하기 때문에 반드시 정렬된 배열에 사용해야 한다.

아래 숫자 3을 찾는 코드를 통해 실제 사용 법을 쉽게 파악할 수 있을 것이다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	vector<int> a {1,2,3,3,3,4};
	cout << lower_bound(a.begin(), a.end(), 3) - a.begin() << '\n';	// 2
	cout << upper_bound(a.begin(), a.end(), 3) - a.begin() << '\n';	// 5
}

 

만약 3이라는 숫자가 없다면 어떻게 될까?

해당 요소가 없을 경우 아래 코드처럼 그 근방 지점을 반환한다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	vector<int> a {2,3,4,5,7};
	
    cout << lower_bound(a.begin(), a.end(), 6) - a.begin() << '\n';	// 4
	cout << upper_bound(a.begin(), a.end(), 6) - a.begin() << '\n';	// 4
	cout << lower_bound(a.begin(), a.end(), 9) - a.begin() << '\n';	// 5
	cout << upper_bound(a.begin(), a.end(), 9) - a.begin() << '\n';	// 5
	cout << lower_bound(a.begin(), a.end(), 0) - a.begin() << '\n';	// 0
	cout << upper_bound(a.begin(), a.end(), 0) - a.begin() << '\n';	// 0    
}