C++ STL lower_bound, upper_bound

lower_bound와 upper_bound에 대해서 포스팅 하겠습니다.

둘 다 컨테이너에 적용할 수 있으며 주어진 범위에서 조건에 맞는 위치를 iterator로 반환합니다.

이진 탐색을 사용하기 때문에 컨테이너는 정렬되어 있어야합니다.

컨테이너 중 vector를 기준으로 자세하게 알아보겠습니다.

---

lower_bound

1) lower_bound의 정의

시작 iterator ~ 끝 iterator 사이에서 value 이상인 값을 가지는 이터레이터를 반환하는 것이 lower_bound입니다.

즉, value와 같거나 큰 값이 처음 나타나는 위치를 iterator로 반환합니다.

 

여담)

value와 같거나 큰 값을 처음 반환하는데 왜 lower_bound라는 이름이 붙었지? 하는 궁금증을 가지게 되어서 사전에 검색해보았습니다.

lower bound는 주어진 집합에서 어떤 원소보다 작거나 같은 원소라는 뜻 입니다.

그래서 반환하는 iterator를 포함(value가 집합에 존재할 때)에서부터 왼쪽 또는 iterator 한 칸 왼쪽(value가 집합에 존재하지 않을 때)이 iterator의 lower_bound가 되는 것 입니다.

 

2) lower_bound의 사용

#include <algorithm>으로 algorithm 헤더 파일을 선언하여야 합니다.

 

vector<int> v; //vector를 선언

vector<int>::iterator iter = lower_bound(v.begin(), v.end(), 22);

 

이렇게 사용하면 vector v에서 22와 같거나 큰 값이 처음 나타나는 위치를 iter에 저장합니다.

---

upper_bound

1) upper_bound의 정의

시작 iterator ~ 끝 iterator 사이에서 value 보다 큰 값(초과 값)을 가지는 이터레이터를 반환하는 것이 upper_bound입니다.

즉, value 보다 큰 값이 처음 나타나는 위치를 iterator로 반환합니다.

 

2) upper_bound의 사용

#include 으로 algorithm 헤더 파일을 선언하여야 합니다.

 

vector<int> v; //vector를 선언

vector<int>::iterator iter = upper_bound(v.begin(), v.end(), 22);

 

이렇게 사용하면 vector v에서 22보다 큰 값이 처음 나타나는 위치를 iter에 저장합니다.

 

이해를 돕기위해 그림을 첨부하였습니다.

---

활용

그렇다면 이것을 어디에 쓰면 좋을지 한번 알아보겠습니다.

오름차순으로 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때 lower, upper bound를 사용할 수 있습니다. (이진 탐색 기반이기 때문에 시간 복잡도를 효과적으로 줄일 수 있습니다.)

 

int main() {

	vector<int> arr = { 1,3,5,5,7,8,8,10,11,12,13,14,15 };
	cout << "6 이상 12 이하의 갯수 : " << upper_bound(arr.begin(), arr.end(), 12) - lower_bound(arr.begin(), arr.end(), 6);

	return 0;
}

 

컨테이너들, iterator에 이어 upper_bound, lower_bound까지 꽤 C++에 관련된 포스팅을 하였는데, 생각보다 유용한 기능들이 참 많습니다. 얼른 체화해서 실전 코딩 문제를 풀때 적용해보고 싶습니다.

이상으로 포스팅 마치겠습니다.