[C++ STL] upper_bound, lower_bound 알아보기
lower_bound
개요
특징
- 이진 탐색(binary_search)의 근간이 된다.
- algorithm 헤더에 포함되어 있다.
설명
- 이진 탐색 기반의 탐색이므로, 배열 또는 리스트가 오름차순 정렬되어 있어야 한다.
- 찾으려고 하는 key 값이 없으면, key 값 이상인 값들 중, 가장 작은 값을 찾는다. 그리고 그 위치를 반환한다. (값 반환 X)
- 값을 얻기 위해서는 * 연산자를 사용한다. (예: *lower_bound(v.begin(), v.end());)
- 같은 수가 여러 개 존재하여도 상관 없다.
자세히 알아보기
선수 항목
- #include <algorithm>
- using namespace std;
사용
- 일반적인 사용 : lower_bound(Iterator first, iterator last, 찾으려는 value);
- 또 다른 사용 : lower_bound(Iterator first, iterator last, 찾으려는 value, comp 함수);
반환 값
- 찾으려는 value보다 작지 않은 값들 중에서 첫 번째 요소를 가리키는 iterator
- 가리키는 iterator의 값을 얻으려면 * 연산자를 이용하여 접근한다.
(예시: *lower_bound(v.first(), v.end(), 5);) - 인덱스 number는 (반환된 iterator) - (첫 번째 요소를 가리키는 iterator)로 얻을 수 있다.
(예시: return_val - v.first()) - 최댓값보다 더 큰 값을 찾고자 하는 경우에는, 마지막 요소 다음 메모리를 가리키는 iterator(end()와 같은)를 반환한다. 따라서, 이 iterator에 접근하면 쓰레기값을 얻을 것이다.
시간 복잡도
- O(lgn)
관련 문제
문제집: binary_search/lower_bound/upper_bound (tpwls1213)
www.acmicpc.net
예시
#include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 5, 5, 6 }; auto ex_1 = std::lower_bound(data.begin(), data.end(), 4); auto ex_2 = std::lower_bound(data.begin(), data.end(), 7); auto ex_3 = std::lower_bound(data.begin(), data.end(), 1); auto ex_4 = std::lower_bound(data.begin(), data.end(), 3); cout << *ex_1; cout << *ex_2; cout << *ex_3; cout << *ex_4; }
// 출력 5 (쓰레기값) 1 3
upper_bound
개요
특징
- 이진 탐색(binary_search)의 근간이 된다.
- algorithm 헤더에 포함되어 있다.
설명
- 이진 탐색 기반의 탐색이므로, 배열 또는 리스트가 오름차순 정렬되어 있어야 한다.
- 찾으려고 하는 key 값이 없으면, key 값 초과인 값들 중, 가장 작은 값을 찾는다. 그리고 그 위치를 반환한다. (값 반환 X)
- 값을 얻기 위해서는 * 연산자를 사용한다. (예: *upper_bound(v.begin(), v.end());)
- 같은 수가 여러 개 존재하여도 상관 없다.
자세히 알아보기
선수 항목
- #include <algorithm>
- using namespace std;
사용
- 일반적인 사용 : upper_bound(Iterator first, iterator last, 찾으려는 value);
- 또 다른 사용 : upper_bound(Iterator first, iterator last, 찾으려는 value, comp 함수);
반환 값
- 찾으려는 value보다 큰 값들 중에서 첫 번째 요소를 가리키는 iterator
- 가리키는 iterator의 값을 얻으려면 * 연산자를 이용하여 접근한다.
(예시: *upper_bound(v.first(), v.end(), 5);) - 인덱스 number는 (반환된 iterator) - (첫 번째 요소를 가리키는 iterator)로 얻을 수 있다.
(예시: return_val - v.first()) - 최댓값보다 더 큰 값을 찾고자 하는 경우에는, 마지막 요소 다음 메모리를 가리키는 iterator(end()와 같은)를 반환한다. 따라서, 이 iterator에 접근하면 쓰레기값을 얻을 것이다.
시간 복잡도
- O(lgn)
관련 문제
문제집: binary_search/lower_bound/upper_bound (tpwls1213)
www.acmicpc.net
예시
#include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 5, 5, 6 }; auto ex_1 = std::upper_bound(data.begin(), data.end(), 4); auto ex_2 = std::upper_bound(data.begin(), data.end(), 7); auto ex_3 = std::upper_bound(data.begin(), data.end(), 1); auto ex_4 = std::upper_bound(data.begin(), data.end(), 3); cout << *ex_1; cout << *ex_2; cout << *ex_3; cout << *ex_4; }
// 출력 5 (쓰레기값) 2 5
'공부 > C, C++' 카테고리의 다른 글
[C++ STL] list 알아보기 (0) | 2020.04.03 |
---|---|
[C++] vector의 reserve()로 push_back() 시간을 줄이자! (0) | 2020.03.19 |
댓글
이 글 공유하기
다른 글
-
[C++ STL] list 알아보기
[C++ STL] list 알아보기
2020.04.03 -
[C++] vector의 reserve()로 push_back() 시간을 줄이자!
[C++] vector의 reserve()로 push_back() 시간을 줄이자!
2020.03.19
댓글을 사용할 수 없습니다.