💡 퀵 접속: cpp.kr/lower_bound

lower_bound

C++ 표준 라이브러리의 알고리즘으로, 정렬된 범위에서 주어진 값보다 크거나 같은 첫 번째 요소의 위치를 반환합니다. 이진 탐색을 사용하여 O(log n) 시간에 수행됩니다.

기본 사용법

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

int main() {
    std::vector<int> v = {1, 2, 3, 3, 3, 4, 5};
    
    // 3보다 크거나 같은 첫 번째 요소 찾기
    auto it = std::lower_bound(v.begin(), v.end(), 3);
    
    // 결과 출력
    std::cout << "3보다 크거나 같은 첫 번째 요소의 위치: " 
              << (it - v.begin()) << std::endl;
    std::cout << "해당 위치의 값: " << *it << std::endl;
    
    return 0;
}

실행 결과:

3보다 크거나 같은 첫 번째 요소의 위치: 2
해당 위치의 값: 3

커스텀 비교 함수 사용

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

int main() {
    std::vector<int> v = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    
    // 내림차순 정렬된 벡터에서 7보다 작거나 같은 첫 번째 요소 찾기
    auto it = std::lower_bound(v.begin(), v.end(), 7,
                              std::greater<int>());
    
    // 결과 출력
    std::cout << "7보다 작거나 같은 첫 번째 요소의 위치: " 
              << (it - v.begin()) << std::endl;
    std::cout << "해당 위치의 값: " << *it << std::endl;
    
    return 0;
}

실행 결과:

7보다 작거나 같은 첫 번째 요소의 위치: 3
해당 위치의 값: 7

사용자 정의 타입에서 사용

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

struct Person {
    std::string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 20},
        {"Bob", 25},
        {"Charlie", 30},
        {"David", 30},
        {"Eve", 35}
    };
    
    // 30세 이상인 첫 번째 사람 찾기
    Person target{"", 30};
    auto it = std::lower_bound(people.begin(), people.end(), target);
    
    // 결과 출력
    std::cout << "30세 이상인 첫 번째 사람: " << it->name << std::endl;
    
    return 0;
}

실행 결과:

30세 이상인 첫 번째 사람: Charlie

참고사항

lower_bound는 algorithm 헤더에 정의되어 있습니다.
탐색하려는 범위는 반드시 정렬되어 있어야 합니다.
기본적으로 < 연산자를 사용하여 비교합니다.
커스텀 비교 함수를 제공할 수 있습니다.
시간 복잡도는 O(log n)입니다.
upper_bound와 함께 사용하여 특정 값의 범위를 찾을 수 있습니다.

함수	설명
lower_bound(first, last, value)	기본 비교 연산자를 사용하여 하한값 찾기
lower_bound(first, last, value, comp)	커스텀 비교 함수를 사용하여 하한값 찾기