C++ STL lower_bound upper_bound 완벽 가이드

🔗 lower_bound와 upper_bound란?

C++ STL에서 제공하는 lower_bound와 upper_bound는 이진 탐색 기반의 함수입니다.
정렬된 컨테이너에서 원하는 위치를 빠르게 찾는 데 사용되며, 특히 검색 범위를 지정하거나 구간을 계산할 때 매우 유용하죠.

두 함수는 모두 헤더에 정의되어 있으며, vector, deque 같은 시퀀스 컨테이너는 물론 map, set 같은 연관 컨테이너에서도 활용할 수 있습니다.

🔍 반환값은 반복자(iterator)

이 함수들은 특정 값을 반환하는 것이 아니라 반복자(iterator)를 반환합니다.
즉, 찾은 위치의 주소를 알려주는 것이며, 이 반복자를 통해 값을 참조하거나 위치 계산에 활용할 수 있어요.

💬 lower_bound는 특정 값 이상이 처음 나오는 위치, upper_bound는 특정 값 초과가 처음 나오는 위치를 가리킵니다.

예를 들어, 정렬된 벡터 {1, 3, 3, 5, 7}에서 lower_bound(3)는 두 번째 요소(3)를, upper_bound(3)는 네 번째 요소(5)를 가리킵니다.

🛠️ 이진 탐색 기반의 동작 원리

lower_bound와 upper_bound는 내부적으로 이진 탐색 알고리즘을 사용하여 요소를 찾습니다.
이진 탐색은 정렬된 데이터를 절반씩 나누며 원하는 값을 찾아가는 방식으로, 매우 빠른 검색 성능을 자랑하죠.

두 함수 모두 시간 복잡도가 O(log N)으로, 데이터가 수만 개 이상이어도 빠르게 위치를 탐색할 수 있습니다.
이는 반복문으로 일일이 탐색하는 것보다 훨씬 효율적이에요.

⚙️ 내부 동작 방식 이해하기

lower_bound는 탐색 중 값이 크거나 같은 위치를 발견하면 그 위치로 범위를 줄입니다.
반면 upper_bound는 값보다 큰 위치를 찾을 때만 이동하므로 기준값보다 큰 최초의 요소를 반환하죠.

이러한 로직은 직접 구현할 수도 있지만, STL의 ready-made 함수를 쓰면 안정성도 높고 코드도 간결해집니다.

vector<int> v = {1, 3, 3, 5, 7};

auto it1 = lower_bound(v.begin(), v.end(), 3); // 첫 번째 3
auto it2 = upper_bound(v.begin(), v.end(), 3); // 3보다 큰 첫 번째 수 (5)

⚙️ lower와 upper 차이와 사용 시기

lower_bound와 upper_bound는 비슷해 보이지만, 아주 중요한 차이점이 존재합니다.
바로 기준값을 포함하느냐 포함하지 않느냐인데요.
이 차이를 명확히 이해하고 있어야 올바른 범위 검색이나 조건 필터링이 가능합니다.

📌 반환 기준 비교

따라서 중복값 포함 여부에 따라 어떤 함수를 써야 할지 달라집니다.
예를 들어 값이 3인 요소를 모두 찾고 싶다면 lower_bound(3)부터 upper_bound(3)까지 범위를 지정하면 되죠.

💬 [lower_bound, upper_bound] 범위는 값이 같은 요소의 구간을 쉽게 추출할 수 있는 강력한 도구입니다.

🔍 사용 예 요약

• 📥값이 존재할 수 있는 최소 위치 찾기 → lower_bound
• 📤값을 넘어서는 첫 위치 찾기 → upper_bound
• 📦중복 요소의 범위 검색 → [lower_bound, upper_bound) 활용

🔌 vector, set, map에서의 활용법

lower_bound와 upper_bound는 다양한 STL 컨테이너에서 사용할 수 있으며,
각 컨테이너의 구조에 따라 활용 방식에도 조금씩 차이가 있습니다.
특히 vector, set, map은 대표적인 대상이죠.

📌 vector에서의 활용

vector는 메모리상 연속된 데이터 구조이기 때문에,
lower_bound와 upper_bound를 헤더에 포함된 함수로 바로 사용할 수 있습니다.

vector<int> v = {1, 2, 4, 4, 5, 6};

auto lb = lower_bound(v.begin(), v.end(), 4); // 첫 번째 4
auto ub = upper_bound(v.begin(), v.end(), 4); // 4를 초과하는 첫 번째 요소 (5)

🌳 set에서의 활용

set은 자동으로 정렬되는 컨테이너이며, lower_bound와 upper_bound는 멤버 함수로 제공됩니다.

set<int> s = {1, 3, 5, 7};

auto lb = s.lower_bound(5); // 5를 가리킴
auto ub = s.upper_bound(5); // 7을 가리킴

🗂️ map에서의 활용

map은 key를 기준으로 정렬되며, 역시 멤버 함수 형태의 lower_bound, upper_bound를 제공합니다.
이 경우 반복자가 std::pair<const Key, Value>를 가리키므로, .first와 .second를 통해 접근합니다.

map<string, int> scores = {
    {"Alice", 85},
    {"Bob", 90},
    {"Charlie", 95}
};

auto it = scores.lower_bound("Bob"); 
cout << it->first << ": " << it->second; // Bob: 90

💡 자주 쓰이는 실전 예제

실제 개발 현장에서 lower_bound와 upper_bound는 매우 다양한 방식으로 사용됩니다.
단순한 검색을 넘어 범위 구간 설정, 중복 요소 필터링, 조건 만족 요소 탐색 등에서 활약하죠.
다음은 실무에 자주 등장하는 패턴 예시입니다.

📍 특정 값의 등장 횟수 세기

vector<int> nums = {1, 2, 3, 3, 3, 4, 5};

int count = upper_bound(nums.begin(), nums.end(), 3) 
          - lower_bound(nums.begin(), nums.end(), 3); 
// count = 3

이 방식은 중복된 값이 몇 개인지 구할 때 매우 유용합니다.
검색된 반복자의 차를 계산하면 곧 개수가 되니까요.

🔎 조건을 만족하는 첫 번째 요소 찾기

vector<int> scores = {60, 65, 70, 80, 90};

auto it = lower_bound(scores.begin(), scores.end(), 75);
if (it != scores.end()) {
    cout << "조건을 만족하는 점수: " << *it; // 출력: 80
}

이처럼 특정 기준 이상/초과의 첫 요소를 빠르게 찾을 수 있어,
탐색 효율성이 중요한 문제에서 자주 활용됩니다.

❓ 자주 묻는 질문 (FAQ)