C++ lower_bound, upper_bound 활용하기

1. 정리

lower_bound와 upper_bound는 정렬된 범위에서 이진 탐색을 수행하는 함수다. 데이터가 커질수록 순차 탐색보다 효율적으로 동작한다.

두 함수 모두 iterator를 반환한다. 배열이나 vector의 인덱스가 필요하면 begin() iterator를 빼면 된다.

vector<int> v = { 0, 1, 2, 3, 4, 5 };
int index;

2. 오름차순 vector

lower_bound는 찾는 값 이상인 첫 요소를 가리킨다. 값 1을 찾으면 인덱스 1을 반환한다.

index = lower_bound(v.begin(), v.end(), 1) - v.begin();
cout << "Index:" << index << endl; // 1

upper_bound는 찾는 값을 초과하는 첫 요소를 가리킨다. 값 1을 찾으면 인덱스 2를 반환한다.

index = upper_bound(v.begin(), v.end(), 1) - v.begin();
cout << "Index:" << index << endl; // 2

3. 내림차순 vector

내림차순 범위는 정렬에 사용한 비교 함수를 탐색에도 동일하게 전달해야 한다. greater<int>()를 사용하면 lower_bound는 이하, upper_bound는 미만의 첫 위치를 찾는다.

v = { 5, 4, 3, 2, 1, 0 };

index = lower_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();
cout << "Index:" << index << endl; // 4

index = upper_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();
cout << "Index:" << index << endl; // 5

정렬 상태와 비교 함수가 탐색 조건과 맞지 않으면 결과를 신뢰할 수 없다. lower_bound는 이상 또는 이하, upper_bound는 초과 또는 미만을 찾는다는 기준으로 구분하면 된다.