C++ STL의 set 컨테이너가 제공하는 lower_bound() 함수는 매개변수로 전달한 키(k)와 같은 값을 갖는 원소를 가리키는 반복자(iterator)를 반환합니다. 만약 키 k가 set에 존재하지 않는다면, k보다 큰 값 중 가장 작은 원소, 즉 바로 다음으로 큰 원소를 가리키는 반복자를 대신 반환합니다.
쉽게 말해 lower_bound(k)는 'k 이상인 첫 번째 원소'의 위치를 알려주는 함수입니다. set은 내부적으로 레드-블랙 트리와 같은 균형 이진 탐색 트리로 구현되어 항상 정렬 상태를 유지하기 때문에, 이진 탐색 방식으로 O(log n) 시간 안에 빠르게 위치를 찾을 수 있습니다.
알고리즘
시작
빈 set 컨테이너 s를 초기화한다.
set 컨테이너를 가리킬 반복자를 선언한다.
s에 원소들을 삽입한다.
주어진 키의 lower bound 값을 찾아 반복자에 저장한다.
찾은 lower bound 값을 출력한다.
종료예제 코드
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> s; // 빈 set 컨테이너 선언
set<int>::iterator iter; // lower bound 값을 가리킬 반복자 선언
// set 컨테이너 s에 원소 삽입
s.insert(7);
s.insert(6);
s.insert(1);
s.insert(4);
s.insert(2);
s.insert(9);
s.insert(10);
// 키를 인자로 전달해 lower bound 탐색
iter = s.lower_bound(4);
cout << "4의 lower bound: " << *iter << endl;
iter = s.lower_bound(5);
cout << "5의 lower bound: " << *iter << endl;
iter = s.lower_bound(8);
cout << "8의 lower bound: " << *iter << endl;
return 0;
}실행 결과
4의 lower bound: 4 5의 lower bound: 6 8의 lower bound: 9
핵심 동작 정리
- 키가 set에 존재하는 경우: 해당 키 원소 자체를 가리키는 반복자를 반환합니다. 위 예제에서 4는 set에 들어 있으므로 4가 그대로 출력됩니다.
- 키가 set에 없는 경우: 키보다 큰 원소 중 가장 작은 값을 가리킵니다. 5는 set에 없으므로 그다음으로 큰 값인 6이 반환됩니다.
- 모든 원소보다 큰 키(예: 30): 조건을 만족하는 원소가 없으므로
end()반복자를 반환합니다. 이 상태에서 역참조(*)하면 미정의 동작(undefined behavior)이 발생하므로, 반드시iter != s.end()검사를 먼저 수행한 뒤 사용해야 합니다.
upper_bound()와의 차이
upper_bound(k)는 k보다 엄격하게 큰 첫 번째 원소를 반환한다는 점에서 lower_bound()와 다릅니다. 키가 set에 존재할 때 lower_bound()는 그 키 자체를 반환하지만, upper_bound()는 그다음 원소를 반환합니다. 두 함수를 함께 활용하면 특정 값의 존재 여부 확인, 구간 내 원소 개수 계산 등 다양한 범위 탐색 문제를 효율적으로 해결할 수 있습니다.