C++ upper_bound , lower_bound 이용하기 / 알고리즘

 

- C++에서 제공하는 이진탐색 기반의 탐색 함수이다.

- 이진 탐색 기반이므로 O(logN)의 복잡도로 탐색이 가능하다.

- 배열은 오름차순 혹은 내림차순으로 정렬이 되어 있어야 한다. 

 

 

1. lower_bound

vector <int> num = { 3,4,4,5,6 };
int idx = lower_bound(num.begin(), num.end(), 4) - num.begin();
cout << idx;

출력 : 1

배열에서 주어진 값과 같거나 큰수인 수가 가장 처음 등장하는 인덱스값을 찾을 때 사용한다. 

lower_bound는 iterator를 반환하기 때문에 인덱스를 바로 알고자 할 경우 vector.begin()을 빼준다. 

배열이라면, 배열의 이름을 빼주면 된다.

 

---

2. upper_bound

vector <int> num = { 3,4,5,7,8 };
int idx = upper_bound(num.begin(), num.end(), 5) - num.begin();
cout << idx;

출력 : 3

배열에서 주어진 값보다 큰 수(초과)가 가장 처음 등장하는 인덱스 값을 찾을 때 이용한다.

예시의 경우 5보다 큰 수인 7이 인덱스 3 이므로 3번째를 리턴한다.

 

 

---

 

3. 사용

 

1) 두개를 함께 사용하여 정렬된 배열에서 a 이상, b 이하 숫자들의 개수를 구하는 데 사용할 수 있다.

vector <int> num = { 3,4,5,7,8,8,11 };
int cnt = upper_bound(num.begin(), num.end(), 10) - lower_bound(num.begin(), num.end(), 5);
cout << cnt;

출력 : 4 (5이상 10 이하 수의 개수)

 

2) 정렬된 배열에서 특정 수가 몇번 나오는지 알고자 할 때 유용

vector <int> num = { 3,4,5,7,8,8,11 };
int cnt = upper_bound(num.begin(), num.end(), 8) - lower_bound(num.begin(), num.end(), 8);
cout << cnt;

출력 : 2 (8의 개수)