[c++] lower_bound, upper_bound 톺아보기

김민주·2023년 7월 5일

숫자의 개수가 많아서 이진탐색으로 원하는 값을 찾으려고 한다.

그런데 숫자에 중복이 존재한다.

그러면 어떤 방법을 써야할까? 바로 lower_bound()와 upper_bound()이다!

lower_bound, upper_bound란?

[first, last) 범위에서 이진탐색으로 원소를 탐색하여,

lower_bound : 찾고자 하는 값보다 같거나 큰 숫자가 처음 등장하는 위치 반환 (없다면 last(v.end()) 반환)
upper_bound : 찾고자 하는 값을 초과하는 값이 가장 처음 나타나는 위치를 반환

참고로 algorithm 헤더에 포함되어 있다.

`lower_bound`

용도 1 : key 값이 가장 처음 등장하는 위치 찾을 때
용도 2 : key 값보다 작은 값들의 개수 구할 때
사용 조건 : 배열이 오름차순 정렬되어 있어야 함 (이진탐색이므로)
예시)
```
#include <iostream>
#include <algorithm>
usingnamespace std;

int main() {

	vector<int> arr= { 1,2,3,4,5,6,6,6 };
	sort(arr.begin(), arr.end());
	cout<< "lower_bound(6) : "<< lower_bound(arr.begin(), arr.end(), 6)- arr.begin();

	// 결과 -> lower_bound(6) : 5
	return 0;
}
```
- [arr.begin(), arr.end()) 범위에서 6이상의 숫자가 처음으로 나오는 위치를 반환하는 예제이다.
- 위 예시에서는 6인 5번째에서 가장 처음 등장했다.
- arr.begin()을 빼준 이유 : lower_bound의 return 값이 iterator이기 때문이다. 실제로 몇 번째 인덱스인지 알고 싶다면 위처럼 배열의 첫번째 주소(arr.begin())을 빼주면 된다.
- 만약 arr이 배열이라면 lower_bound(arr, arr+8, 6) - arr 로 해주면 된다.

`upper_bound`

용도 1 : key 값보다 큰 값이 처음 등장하는 위치 찾기
용도 2 : key 값보다 큰 값의 개수 구할 때
사용 조건 : 배열이 오름차순 정렬되어 있어야 함 (이진탐색이므로)

예시)

#include <iostream>
#include <algorithm>
usingnamespace std;

int main() {

	vector<int> arr= { 1,2,3,4,5,6 };
	sort(arr.begin(), arr.end());
	cout<< "upper_bound(3) : "<< upper_bound(arr.begin(), arr.end(), 3)- arr.begin();

	// 결과 -> upper_bound(3) : 3
	return 0;
}

[arr.begin(), arr.end()) 범위에서 3 초과의 숫자가 처음으로 나오는 위치를 반환하는 예제이다.
위 예시에서는 3초과하는 숫자가 4로 3번째에 처음 등장했다.
lower_bound와 동일하게 iterator를 return한다.

🔑 이런 문제에서 활용할 수 있어요!

📌 중복 배열에서 특정한 숫자가 몇 번 나오는지 찾고자 할 때

lower_bound와 upper_bound를 함께 사용하여 O(logN)으로 탐색 가능하다

예시)

int main() {

	vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 };
	sort(arr.begin(), arr.end());
	cout << "5의 개수 : " << upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5);

	// 결과 -> 5의 개수 : 3
	return 0;
}

upper_bound : 5 인덱스 반환
lower_bound : 2 인덱스 반환
따라서 결과는 3이 된다

📌 특정 범위에 속하는 숫자가 몇 개 있는지 탐색하고자 할 때

lower_bound와 upper_bound를 함께 사용하여 O(logN)으로 탐색 가능하다

예시)

int main() {

	vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
	cout << "5 이상 11 이하의 개수 : " << upper_bound(arr.begin(), arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5);
	
	// 결과 -> 5이상 11 이하의 개수 : 8
	return 0;
}

upper_bound : 10 인덱스 반환
lower_bound : 2 인덱스 반환
따라서 결과는 8이 된다