[C++/Algorithm] upper_bound, lower_bound 이해하기

2021년 상반기 카카오 인턴 코딩 테스트에 응시했었는데, 당시 3번 문제에 upper_bound, lower_bound를 사용했었다.

 

그 당시에 조금 헤맸던 기억이 있어서 이번 기회에 한번 정리해보려 한다.

 

우선 c++ reference(https://www.cplusplus.com/reference/algorithm/upper_bound/)를 찾아보면 

 

Return iterator to upper bound

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

The elements are compared using operator< for the first version, and comp for the second. The elements in the range shall already be sorted according to this same criterion (operator <or comp), or at least partitioned with respect to val.

The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for random-access iterators.

Unlike lower_bound, the value pointed by the iterator returned by this function cannot be equivalent to val, only greater.

 

다음과 같이 저술되어 있다.

 

첫 문장을 보면 내가 입력한 value보다 큰 첫 번째 원소를 가리키는 iterator를 반환한다 라고 되어있다.

 

즉 1 1 2 2 2 3 3과 같은 배열에서 2를 입력값으로 주면 3의 첫 위치(1 1 2 2 2 3 3)를 가리키는 iterator를 반환한다고 되어있다.

 

두 번째 문단을 살펴보면, upper bound에는 두 가지 버전이 있는데 두 버전의 원형은 다음과 같다.

 

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

 

이를 보면 첫 번째 버전은 별도의 비교 연산을 정의하지 않은 상태로, 시작 위치, 종료 위치, 값 이렇게 세 개만 인자로 전달하는 것을 볼 수 있고, 두 번째 버전은 비교 연산을 인자로 같이 전달하여 함수를 호출하는 것을 볼 수 있다.

 

첫 번째 버전은 별도의 비교 연산을 정의하지 않았기 때문에 < 즉 우리가 기본적으로 알고 있는 오름차순으로 정렬되어 있다고 가정한다. 

 

그리고 val 바로 다음 원소의 시작 iterator를 반환하기 때문에 절대로 val과 같은 값을 가리키는 iterator가 반환될 수 없다고 되어있다.

 

비슷한 맥락으로 lower bound에 대한 reference도 참고해 보길 바란다. (https://www.cplusplus.com/reference/algorithm/lower_bound/)

 

간략히 요약하자면, lower bound의 경우 

Returns an iterator pointing to the first element in the range [first, last) which does not compare less than val.

 

즉 val보다 작지 않은 첫 번째 원소의 시작점을 반환한다고 되어있다.

 

위의 내용을 바탕으로 간단한 예시 코드를 한번 작성해 보았다.

 

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> vec;
	
	vec.push_back(1);
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(2);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(3);
	
	// 1 1 2 2 2 3 3
	
	
	int ub = *upper_bound(vec.begin(), vec.end(), 2); // 3
	int lb = *lower_bound(vec.begin(), vec.end(), 2); // 2
	
	int ub_range = (int) (upper_bound(vec.begin(), vec.end(), 2) - vec.begin());
	int lb_range = (int) (lower_bound(vec.begin(), vec.end(), 2) - vec.begin());
	
	cout << ub << " " << lb << endl; 
	cout << ub_range << " " << lb_range << endl;
	
	return 0;
}

 

vector에 int형으로 1, 1, 2, 2, 2, 3, 3을 입력하였고, 별도의 compare함수는 정의하지 않았다.

 

위의 내용을 바탕으로 도식화해보면 upper_bound, lower_bound가 반환하는 iterator가 가리키는 위치는 

 

다음과 같다.

 

즉 val값으로 2를 주었을 때 lower_bound의 경우 2보다 작지 않은 값 (=2)의 시작점의 위치를 가리키게 되고,

upper_bound의 경우 2보다 큰 값 (=3)의 시작점의 위치를 가리키게 된다.

 

따라서 위의 코드를 실행하였을 때 나타나는 결괏값은 

 

3, 2 -> 각각 iterator가 가리키는 주소의 값

 

5, 2 -> 각각 iterator가 가리키는 주소가 시작점으로부터 몇 번째 인덱스인지 확인 

 

으로 예측할 수 있다.

 

실제로 확인해보면,

 

 

예측한 결과대로 나오는 것을 확인할 수 있다.

 

그러면 만약에 배열에 없는 값을 val로 주면 어떻게 될까?

 

int ub_range = (int) (upper_bound(vec.begin(), vec.end(), 0) - vec.begin());
int lb_range = (int) (lower_bound(vec.begin(), vec.end(), 4) - vec.begin());

 

주어진 코드를 다음과 같이 수정하여 실행해 보았다.

 

lower bound의 경우 val보다 작지 않은, 즉 이상이 되는 첫 번째 값을 가리키는 iterator를 반환하기 때문에 아마 0번째 인덱스가 반환될 것이라 예측되고, upper bound의 경우 val보다 큰 첫번째 원소를 가리키는 iterator를 반환하기 때문에 배열의 마지막 원소인 6번 인덱스의 다음인 7번이 반환될 것이라 예측할 수 있다. 

 

 

다음과 같이 출력되는 것을 확인할 수 있다.

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.