[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)

예시

#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)

예시

#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