lower_bound와 upper_bound

두 함수 모두 C++에서 이진 탐색을 활용하여 원소의 위치를 찾아낼때 활용한다.

공통적으로 아래 두 가지 특징을 지니고 있다.

 

1. 배열, 혹은 벡터가 오름차순으로 정렬되어있어야 함

2. algorithm 라이브러리를 사용함

---

lower_bound 

• 목적 : 찾으려는 key 값이 배열, 혹은 벡터의 몇 번째에 존재하는지 반환
• Tip 1 : key값이 존재하지 않을 경우, 찾으려는 key값보다 바로 다음으로 큰 값의 위치를 반환
            (ex : 아래 예시에서 -1의 lower_bound 결과를 찾을 경우, 0을 반환)
• Tip 2 : key값과 key값보다 큰 값 모두 존재하지 않을 경우, 배열의 size를 반환함
            (ex : 아래 예시에서 6을 찾을 경우 5를 반환)

사용법

// 사용법 
lower_bound(배열, 배열+배열의 사이즈, 찾고자 하는 값) - 배열
lower_bound(벡터.begin(), 벡터.end(), 찾고자 하는 값) - 벡터.begin() 

사용 예시

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int arr[] = {0,1,4,3,2};
    sort(arr,arr+5); // {0,1,2,3,4}
    cout << "Lower Bound (2) : " << lower_bound(arr,arr+5,2)-arr << "\n";
    return 0;
}

 

사용 결과

Lower Bound (2) : 2

---

upper_bound

• 목적 : 찾으려는 key 값보다 바로 다음으로 큰 값이 배열 혹은 벡터의 몇 번째에 존재하는지 반환
• Tip 1 : key값이 존재하지 않을 경우, 찾으려는 key값보다 바로 다음으로 큰 값의 위치를 반환
            (ex : 아래 예시에서 -1의 upper_bound 결과를 찾을 경우, 0을 반환)
• Tip 2 : key값과 key값보다 큰 값 모두 존재하지 않을 경우, 배열의 size를 반환함
            (ex : 아래 예시에서  5의 upper_bound 결과를 찾을 경우, 5를 반환)

사용법

// 사용법 
upper_bound(배열, 배열+배열의 사이즈, 찾고자 하는 값) - 배열
upper_bound(벡터.begin(), 벡터.end(), 찾고자 하는 값) - 벡터.begin() 

사용 예시

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int arr[] = {0,1,4,3,2};
    sort(arr,arr+5); // {0,1,2,3,4}
    cout << "Upper Bound (2) : " << upper_bound(arr,arr+5,2)-arr << "\n";
    return 0;
}

사용 결과

Upper Bound (2) : 3 // 2보다 큰 값인 3은 3번째 인덱스에 존재한다.