[Algorithm / C++] lower_bound, upper_bound

이진 탐색 기반의 탐색 방법으로, 사용 전에 배열이나 리스트가 오름차순 정렬되어 있어야 한다.

 

lower_bound

찾는 값과 같거나, 찾는 값보다 큰 가장 작은 정수값의 위치를 찾아주는 함수

• 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있다.

// 구현

int lower_bound(int size, int key, int arr[])
{
    int start = 0;
    int end = size;
    int mid = 0;
    
    while (start < end)
    {
        mid = (start + end) / 2;
        if (arr[mid] < key) start = mid + 1;
        else end = mid;
    }
    return (end + 1);
}

// STL
#include <algorithm>
int main(void)
{
    int array[];
    vector<int> arr;

    lower_bound (arr.begin(), arr.end(), key) - arr.begin();
    lower_bound (array, array + n, key) - array);
}

 

upper_bound

찾는 값을 초과하는 가장 첫 번째 원소의 위치를 찾아주는 함수

• 같은 원소가 여러개 존재해도 항상 유일한 해를 구할 수 있다.

// 직접 구현
int upper_bound(int size, int key, int arr[])
{
    int start = 0;
    int end = size;
    int mid;
    
    while (start < end)
    {
        mid = (start + end) / 2;
        if (arr[mid] <= key) start = mid + 1;
        else end = mid;
    }
    return (end + 1);
}

// STL
#include <algorithm>

int main(void)
{
    int arr[];
    vector<int> array;
    upper_bound(arr, arr + size, key) - arr;
    upper_bound(array.begin(), array.end(), key) - array.begin();
}