💡 퀵 접속: cpp.kr/upper_bound

upper_bound

C++ 표준 라이브러리의 알고리즘으로, 정렬된 범위에서 주어진 값보다 큰 첫 번째 요소의 위치를 찾습니다. upper_bound는 이진 탐색을 사용하여 O(log n) 시간에 동작하며, 원본 범위를 수정하지 않습니다. 이 함수는 정렬된 범위에서만 사용할 수 있습니다.

기본 사용법

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {1, 2, 2, 2, 3, 3, 4, 5};
    
    std::cout << "벡터: ";
    for (int x : v) std::cout << x << " ";
    std::cout << std::endl;
    
    // 2보다 큰 첫 번째 요소 찾기
    auto it = std::upper_bound(v.begin(), v.end(), 2);
    
    if (it != v.end()) {
        std::cout << "2보다 큰 첫 번째 요소: " << *it << std::endl;
        std::cout << "위치: " << (it - v.begin()) << std::endl;
    } else {
        std::cout << "2보다 큰 요소를 찾을 수 없습니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

벡터: 1 2 2 2 3 3 4 5
2보다 큰 첫 번째 요소: 3
위치: 4

문자열에서 사용

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string s = "aabbccddee";
    
    std::cout << "문자열: " << s << std::endl;
    
    // 'b'보다 큰 첫 번째 문자 찾기
    auto it = std::upper_bound(s.begin(), s.end(), 'b');
    
    if (it != s.end()) {
        std::cout << "'b'보다 큰 첫 번째 문자: " << *it << std::endl;
        std::cout << "위치: " << (it - s.begin()) << std::endl;
    } else {
        std::cout << "'b'보다 큰 문자를 찾을 수 없습니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

문자열: aabbccddee
'b'보다 큰 첫 번째 문자: c
위치: 4

사용자 정의 타입에서 사용

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

class Person {
    std::string name;
    int age;
public:
    Person(const std::string& n, int a) : name(n), age(a) {}
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
    
    void print() const {
        std::cout << name << " (" << age << "세)" << std::endl;
    }
};

int main() {
    std::vector<Person> v = {
        Person("Alice", 20),
        Person("Bob", 30),
        Person("Charlie", 30),
        Person("David", 40),
        Person("Eve", 50)
    };
    
    std::cout << "벡터:" << std::endl;
    for (const auto& p : v) p.print();
    
    // 30세보다 나이가 많은 첫 번째 사람 찾기
    auto it = std::upper_bound(v.begin(), v.end(), Person("", 30));
    
    if (it != v.end()) {
        std::cout << "\n30세보다 나이가 많은 첫 번째 사람:" << std::endl;
        it->print();
        std::cout << "위치: " << (it - v.begin()) << std::endl;
    } else {
        std::cout << "\n30세보다 나이가 많은 사람을 찾을 수 없습니다." << std::endl;
    }
    
    return 0;
}

실행 결과:

벡터:
Alice (20세)
Bob (30세)
Charlie (30세)
David (40세)
Eve (50세)

30세보다 나이가 많은 첫 번째 사람:
David (40세)
위치: 3

참고사항

  • upper_bound는 algorithm 헤더에 정의되어 있습니다.
  • 원본 범위를 수정하지 않습니다.
  • 시간 복잡도는 O(log n)입니다.
  • 정렬된 범위에서만 사용할 수 있습니다.
  • 요소를 찾지 못하면 last를 반환합니다.
  • 사용자 정의 타입에 대해서는 operator<가 정의되어 있어야 합니다.
  • 커스텀 비교 함수를 사용할 수 있습니다.
  • lower_bound는 주어진 값보다 작지 않은 첫 번째 요소를 찾는 버전입니다.
  • binary_search는 주어진 값이 존재하는지 확인하는 버전입니다.
  • equal_range는 주어진 값과 같은 요소들의 범위를 찾는 버전입니다.
함수 설명
upper_bound(first, last, value) [first, last) 범위에서 value보다 큰 첫 번째 요소의 위치를 반환
upper_bound(first, last, value, comp) [first, last) 범위에서 comp(value, element)가 true인 첫 번째 요소의 위치를 반환