[C++] Upper_bound, Lower_bound

개요

C++에서 이분 탐색으로 원소를 탐색하는 함수 중 하나이다.

두 함수를 사용하기 위해서는 algorithm 헤더의 include가 필요하다.

또한, 이분 탐색 특성상 배열이 오름차순으로 정렬되어 있어야한다.

설명

upper_bound : 배열에서 key값을 초과하는 수의 iterator 중, 가장 작은 iterator 반환 

lower_bound : 배열에서 key값 이상의 수의 iterator 중, 가장 작은 iterator 반환

두 함수 모두 해당하는 수가 없다면, end iterator를 반환한다.

iterator 타입을 반환하므로, 인덱스로 바꿔주고 싶으면 begin 등으로 빼주면 된다.

예제

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int main()
{
    vector<int> v = { 1,3,4,4,4,5,6 };
    auto a = upper_bound(v.begin(), v.end(), 4) - v.begin();
    auto b = lower_bound(v.begin(), v.end(), 4) - v.begin();
    cout << "upper_bound(4) : " << a << endl;
    cout << "lower_bound(4) : " << b;
    return 0;
}

upper_bound : 4를 초과하는 수 중 가장 작은 인덱스는 5가 있는 위치인 v[5]이다.

lower_bound : 4이상의 수 중 가장 작은 인덱스는 첫번째 4가 등장하는 위치인 v[2]이다.

응용

정렬된 배열에서 특정 원소의 개수를 구할 때나, 범위를 만족하는 원소의 개수를 빠르게 찾을 수 있다.

a (이상 / 초과) b (이하 / 미만)의 수를 찾고 싶을 때

a 이상일 땐 lower_bound(a), a 초과일 땐 upper_bound(a)

b 이하일 땐 upper_bound(b), b 미만일 땐 lower_bound(b)

그 이후에 b - a를 해주면 개수를 셀 수 있다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int main()
{
    vector<int> v = { 1,2,3,3,4,4,4,5,6 };
 
    // 4이상 6미만의 수 구하기
    int result1 = lower_bound(v.begin(), v.end(), 6) - lower_bound(v.begin(), v.end(), 4);
 
    // 4의 개수 구하기
    int result2 = upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);
 
    cout << result1 << ' ' << result2;
    return 0;
}

1. 3 "이상" , 6 "미만" 이므로 lower_bound(6)에서 lower_bound(3)를 빼주면 된다.

2. 4의 개수는 4 "이상", 4 "이하"의 수를 구하는 것과 똑같다.

따라서 upper_bound(4)에서 lower_bound(4)를 빼주면 됨.