[C++] lower_bound, upper_bound

정의

#include <algorithm>

오름차순 정렬되어 있는 원소를 이분탐색으로 구한다

 

lower_bound

기본적으로 key를 찾고, 존재하지 않으면 초과하면서 가장 작은 원소를 찾는다

• 예시

key가 5일 때
배열 원소	1	2	5	7	10	11

key가 8일 때
배열 원소	1	2	5	7	10	11

• STL

코드
1차원 벡터	vector<int> vec
value	*lower_bound(vec.begin(), vec.end(), num)
index	lower_bound(vec.begin(), vec.end(), num) - vec.begin()

 

예시 코드

int lowerbound(const vector<int>& vec, int x) {
    const int n = vec.size();
    int lo = -1, hi = n;
    
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (vec[mid] < x) lo = mid;
        else hi = mid;
    }
    
    return hi;
}

 

upper_bound

key를 초과하면서 가장 작은 원소를 찾는다

• 예시

key가 5일 때
배열 원소	1	2	5	7	10	11

key가 8일 때
배열 원소	1	2	5	7	10	11

• STL

코드
1차원 벡터	vector<int> vec
value	*upper_bound(vec.begin(), vec.end(), num)
index	upper_bound(vec.begin(), vec.end(), num) - vec.begin()

 

예시 코드

int upperbound(const vector<int>& vec, int x) {
    const int n = vec.size();
    int lo = -1, hi = n;
    
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (vec[mid] <= x) lo = mid;
        else hi = mid;
    }
    
    return hi;
}

 

Key의 개수 빠르게 구하기

• lower_bound로 num 값보다 크거나 같은 첫 번째 요소의 위치를 찾음 
  • 즉, num의 가장 처음 위치
• upper_bound로 num 값보다 큰 첫 번째 요소의 위치를 찾음 
  • 즉, num의 가장 마지막 다음 위치

 

마지막+1과 처음 위치의 차이를 계산해서 key의 갯수를 구함

upper_bound(vec.begin(), vec.end(), num) - lower_bound(vec.begin(), vec.end(), num);