이 영역을 누르면 첫 페이지로 이동
hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

페이지 맨 위로 올라가기

hoonDEV

[C++ STL] upper_bound, lower_bound 알아보기

  • 2020.04.03 03:15
  • 공부/C, C++

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

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [C++ STL] list 알아보기

    [C++ STL] list 알아보기

    2020.04.03
  • [C++] vector의 reserve()로 push_back() 시간을 줄이자!

    [C++] vector의 reserve()로 push_back() 시간을 줄이자!

    2020.03.19
다른 글 더 둘러보기

정보

hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

  • hoonDEV의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그

카테고리

  • 분류 전체보기 (91)
    • 일상 (13)
      • 후기 (1)
      • 계획 (11)
    • 공지사항 (1)
    • 알고리즘 (54)
      • 문제풀이 (53)
      • 이론 (1)
    • 공부 (19)
      • React (0)
      • Angular (5)
      • Java (3)
      • C, C++ (3)
      • JavaScript (6)
      • WEB (2)
    • 디자인 (1)
      • UI, UX (1)
    • 개발 (0)
      • boom (0)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • 알고리즘
  • 백준
  • 그리디
  • javascript
  • dp
  • 이분탐색
  • 문제풀이
  • es6

나의 외부 링크

정보

훈개발자의 hoonDEV

hoonDEV

훈개발자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 훈개발자. Designed by Fraccino.

티스토리툴바