정렬된 데이터를 이진탐색으로 슬라이싱 하기(lower_bound, upper_bound)

[0, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9]

위 처럼 정렬된 데이터가 있을때, 특정 값을 기준으로 그 보다 낮거나 높은 값들의 갯수를 구하고 싶다.

가령 3보다 낮은 값은 [0, 1, 2] 3개이며, 높은 값은 [4,  5,  6,  7,  8,  9] 6개이다.

이를 구하는 방법은 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    vector<int> vi = { 0, 1,2,3,3,3, 4,5,6,7,8,9 };
 
    vector<int>::iterator it;
    
    it = lower_bound(vi.begin(), vi.end(), 3);
    cout << it - vi.begin() << endl;
 
    it = upper_bound(vi.begin(), vi.end(), 3);
    cout << vi.end() - it << endl;
 
    return 0;
}

 

만약 위에서 '3'이라는 기준값을 포함한 범위를 구하고 싶으면 lower_bound와 upper_bound를 서로 바꿔 사용하면 된다.