C++ lower_bound() 함수 완벽 가이드: 사용법과 예제

이 글에서는 C++ STL의 lower_bound() 함수에 대해 자세히 알아보겠습니다.

C++의 lower_bound() 메서드는 컨테이너 객체에서 주어진 값보다 작지 않은(즉, 값 이상인) 첫 번째 요소를 가리키는 반복자(iterator)를 반환하는 함수입니다. 이 함수는 내부적으로 이진 탐색(binary search) 알고리즘을 기반으로 동작하기 때문에, 정확한 결과를 얻으려면 탐색 대상 컨테이너가 반드시 사전에 오름차순으로 정렬되어 있어야 합니다.

lower_bound()의 동작 방식

lower_bound()는 지정된 탐색 범위 내에서 다음과 같이 동작합니다.

• 주어진 값과 같거나 큰 첫 번째 요소의 위치를 반환합니다.
• 해당 값이 범위 내에 존재하지 않으면, 그 값이 삽입될 수 있는 적절한 위치를 반환합니다.
• 모든 요소가 주어진 값보다 작다면, 범위의 끝(end) 반복자를 반환합니다.

예제 코드

#include <bits/stdc++.h>
int main(){
    std::vector<int> v{ 10, 20, 30, 40, 50 };
    std::cout << "Vector contains :";
    for (unsigned int i = 0; i < v.size(); i++)
        std::cout << " " << v[i];
    std::cout << "\n";
    std::vector <int>::iterator low1, low2;
    low1 = std::lower_bound(v.begin(), v.end(), 35);
    low2 = std::lower_bound(v.begin(), v.end(), 55);
    std::cout
        << "\nlower_bound for element 35 at position : "
        << (low1 - v.begin());
    std::cout
        << "\nlower_bound for element 55 at position : "
        << (low2 - v.begin());
    return 0;
}

실행 결과

Vector contains : 10 20 30 40 50
lower_bound for element 35 at position : 3
lower_bound for element 55 at position : 5

결과 분석

위 실행 결과를 살펴보면 다음과 같은 의미를 확인할 수 있습니다.

• 값 35의 경우: 벡터에 35라는 요소는 실제로 존재하지 않지만, 30과 40 사이에 위치할 수 있으므로 인덱스 3(값 40의 위치)을 반환합니다.
• 값 55의 경우: 벡터의 모든 요소가 55보다 작기 때문에, 55가 삽입될 수 있는 마지막 위치인 인덱스 5, 즉 범위의 끝(end)을 반환합니다.

이처럼 lower_bound()는 값의 존재 여부와 관계없이 항상 유효한 삽입 위치를 반환하기 때문에, 정렬된 데이터에서 특정 값의 경계를 찾거나 이진 탐색 기반 로직을 구현할 때 매우 유용하게 활용됩니다.