특정 값 시작 지점, 초과 지점 찾기 lower_bound(), upper_bound()

🔎 lower_bound(), upper_bound()

lower_bound(): 정렬된 배열에서 특정 값이 시작되는 지점의 이터레이터를 반환
upper_bound(): 정렬된 배열에서 특정 값을 초과하는 지점의 이터레이터를 반환

만약 배열 내에 value에 해당하는 값이 없는 경우
lower_bound(), upper_bound() 모두 value보다 큰 값 중에 가장 작은 값을 가진 지점의 이터레이터를 반환한다.

ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

사용 예시

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a { 3, 5, 5, 8, 8, 8, 10, 12 };

    //value가 존재하는 경우 (ex. 8)
    cout << "8이 시작되는 지점은 ";
    cout << lower_bound(a.begin(), a.end(), 8) - a.begin() << "번째 인덱스\n";
    cout << "8을 초과하는 지점은 ";
    cout << upper_bound(a.begin(), a.end(), 8) - a.begin() << "번째 인덱스\n\n";

    //value가 존재하지 않는 경우 (ex. 1, 13)
    cout << "1이 없으므로 1보다 큰 값이 시작되는 지점은 ";
    cout << lower_bound(a.begin(), a.end(), 1) - a.begin() << "번째 인덱스\n";
    cout << "13이 없으므로 처음으로 13을 초과하는 지점은 ";
    cout << upper_bound(a.begin(), a.end(), 13) - a.begin() << "번째 인덱스\n";

    return 0;
}

실행 결과

8이 시작되는 지점은 3번째 인덱스
8을 초과하는 지점은 6번째 인덱스

1이 없으므로 1보다 큰 값이 시작되는 지점은 0번째 인덱스
13이 없으므로 처음으로 13을 초과하는 지점은 8번째 인덱스

🔎 특정 값의 개수 구하기

lower_bound(), upper_bound()를 이용하면 배열 내에서 특정 값이 몇 개 있는 지 알 수 있다. lower_bound()는 시작지점, upper_bound()는 그것보다 큰 값의 시작지점을 리턴하므로
단순히 upper_bound()에서 lower_bound()를 빼면 특정 값의 개수가 나온다.

사용 예시

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a { 3, 5, 5, 8, 8, 8, 10, 12 };

    cout << "배열 내에서 8의 개수는 ";

    cout << upper_bound(a.begin(), a.end(), 8) - lower_bound(a.begin(), a.end(), 8) << "개\n";

    return 0;
}

실행 결과

배열 내에서 8의 개수는 3개