C++ lower_bound, upper_bound 사용법

ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

 

lower_bound, upper_bound는 <algorithm> 헤더에 들어 있습니다.

 

두 함수가 정상적으로 작동하기 위해서는 먼저 \([first, last)\) 범위 내의 원소들이 비내림차순(≈오름차순)으로 정렬되어 있어야 합니다. 이진탐색으로 구현되기 때문입니다.

 

각 함수 설명은 다음과 같습니다.

lower_bound(first, last, x)는 \([first, last)\) 범위에서 x 이상인 첫 번째 원소의 위치를 반환합니다.

upper_bound(first, last, x)는 \([first, last)\) 범위에서 x를 초과하는 첫 번째 원소의 위치를 반환합니다.

4번째 인자로 Comparator가 들어갈 수 있습니다.

 

vector<int> v = { -2, -2, -1, -1, 0, 0, 0, 1, 1 };
cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << '\n';  // 4
cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << '\n';  // 7

예시입니다.

lower_bound(0)에서 0 이상인 값이 처음으로 나오는 인덱스 4가 반환되고, upper_bound(0)에서는 0을 초과하는 값이 처음 나오는 인덱스 7이 반환됩니다.

 

시간복잡도는 O(log n)입니다만 Random Access가 가능한 Iterator가 있는 경우만 해당됩니다.

set, multiset같은 경우 랜덤액세스가 안되기 때문에 클래스 내의 lower_bound 메소드를 써야 시간복잡도가 O(log n)이 나옵니다. 함수를 사용하면 O(n)입니다.