lower_bound(), upper_bound()

출처 및 참고 : 

https://www.crocus.co.kr/913

https://yunsu3042.github.io/devlog/2018/02/15/%EB%B0%B1%EC%A4%80-2957%EB%B2%88-C++/

vector<int> v;

lower_bound()

 1. vector에서 lower_bound()를 사용할 때는 정렬되어 있어야 한다.

2. 인덱스(index)를 받환 받기 위해서는 lower_bound( ~ ) - vector.begin()을 사용한다.

3. value가 있다면, value를 반환한다.

4. value가 없다면, value보다 큰 값 중 가장 작은 값을 반환한다.

5. 이상의 개념

6. 반환하는 값 자체가 없다면, vector에서는 v.end()를 반환

upper_bound()

1. vector에서 lower_bound()를 사용할 때는 정렬되어 있어야 한다.

2. 인덱스(index)를 받환 받기 위해서는 upper_bound( ~ ) - vector.begin()을 사용한다.

3. value보다 큰 값 중 가장 작은 값을 반환한다. 즉, {1, 2, 2, 2, 3}에서 2를 찾으려고 하면, 3을 반환(값이라고 가정했을 때)

4. 초과의 개념

5. 반환하는 값 자체가 없다면, vector에서는 v.end()를 반환

#include <bits/stdc++.h>
#include <unordered_map>
 
using namespace std;
 
vector<int> A, B, C, D, ab, cd;
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
 
    vector<int> v = { 1, 2, 3, 3, 3, 3, 4, 5 };
                    //0, 1, 2, 3, 4, 5, 6, 7 
    int idx = lower_bound(v.begin(), v.end(), 3) - v.begin(); // 2
    int idx2 = upper_bound(v.begin(), v.end(), 3) - v.begin(); // 6
 
    // 3의 개수 = 6 - 2 = 4
    printf("%d %d\n", idx, idx2);
 
    return 0;
}

vector : lower_bound(v.begin(), v.end(), value);

map : m.lower_bound(value);

결과 화면

vector v의 원소들
인덱스 =  0  1  2  3  4  5  6  7  8  9 10
원소   =  1  2  3  4  6  7  8  9 10 11 12
 
lower_bound(v.begin(), v.end(), 6) = 6
인덱스 = 4
 
lower_bound(v.begin(), v.end(), 5) = 6
인덱스 = 4
 
upper_bound(v.begin(), v.end(), 6) = 7
인덱스 = 5
 
upper_bound(v.begin(), v.end(), 5) = 6
인덱스 = 4
 
lower_bound(v.begin(), v.end(), 13) = 값 존재 X, 그에 따른 정보 존재 X
 
upper_bound(v.begin(), v.end(), 13) = 값 존재 X, 그에 따른 정보 존재 X

코드

#include <iostream>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <unordered_map>  
#include <unordered_set>  
#include <tuple>
#include <sstream>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
int main(void)
{
    vector<int> v = { 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12 };
 
    printf("vector v의 원소들\n");
 
    printf("인덱스 = ");
    for (int i = 0; i < v.size(); i++) printf("%2d ", i);
    printf("\n");
    printf("원소   = ");
    for (int i = 0; i < v.size(); i++) printf("%2d ", v.at(i));
 
    printf("\n\n");
 
    auto itr = lower_bound(v.begin(), v.end(), 6);
    cout << "lower_bound(v.begin(), v.end(), 6) = " << *itr << '\n';
    printf("인덱스 = %d\n", itr - v.begin());
    printf("\n");
 
    itr = lower_bound(v.begin(), v.end(), 5);
    cout << "lower_bound(v.begin(), v.end(), 5) = " << *itr << '\n';
    printf("인덱스 = %d\n", itr - v.begin());
    printf("\n");
 
    itr = upper_bound(v.begin(), v.end(), 6);
    cout << "upper_bound(v.begin(), v.end(), 6) = " << *itr << '\n';
    printf("인덱스 = %d\n", itr - v.begin());
    printf("\n");
 
    itr = upper_bound(v.begin(), v.end(), 5);
    cout << "upper_bound(v.begin(), v.end(), 5) = " << *itr << '\n';
    printf("인덱스 = %d\n", itr - v.begin());
    printf("\n");
 
    itr = lower_bound(v.begin(), v.end(), 13);
    if (itr == v.end()) printf("lower_bound(v.begin(), v.end(), 13) = 값 존재 X, 그에 따른 정보 존재 X\n");
    printf("\n");
 
    itr = upper_bound(v.begin(), v.end(), 13);
    if (itr == v.end()) printf("upper_bound(v.begin(), v.end(), 13) = 값 존재 X, 그에 따른 정보 존재 X\n");
    printf("\n");
 
    return 0;
}