lower_bound, upper_bound 란?
c++에서는 이진탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공한다
lower_bound
•
용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지를 찾기 위함
•
사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬이 되어있어야한다.
사용법 (배열)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[6] = { 1,2,3,4,5,6 };
cout << "lower_bound(6) : " << lower_bound(arr, arr+6, 6) - arr;
// 결과 --> lower_bound(6) : 5
return 0;
}
C++
복사
•
arr 부터 끝까지 탐색하면서, 6 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제
•
lower_bound의 반환성은 Iterator 이므로, 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼주면 된다.
•
벡터의 경우에는 아래와 같이 v.begin()을 빼주면 된다.
사용법 (벡터)
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = { 1,2,3,4,5,6,6,6 };
cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();
// 결과 -> lower_bound(6) : 5
return 0;
}
C++
복사
upper_bound
•
용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
•
사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬이 되어있어야한다.