lower_bound() & upper_bound()

정렬된 배열에서 어떤 값이 나오는 첫번째 지점 또는 초과하는 지점의 위치를 찾으려면 어떻게 해야할까?

 

또한 이분 탐색을 쉽게 함수로 구현하려면 어떻게 해야할까?

 

이분탐색은 또뭔가?

이분탐색

하나의 알고리즘으로 정렬되어 있는 배열이나 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법

 

 

 

일단 위의 사진이 lowerbound와 upperbound를 설명하는 그림이다.

 

저게 뭐누.. 뭔그림이여

 

그래도 우리는 할 수 있다 하나씩 생각해보자.

 

보면

엄 안보이니까 그림 한번만 더 쓸게요

 

위 그림에서 보면 중복된 값이 있는 배열을 정렬한 상태에서 3을 기준으로 lower_bound(3)을 호출하면 3보다 크면서 큰 값이 최초로 발견된 index를 반환해줍니다.

즉 위에서는 3을 반환하죠

0, 1, 2, 3 이렇게 말이에요

upper_bound(3)은 3보다 큰 값이 제일 처음 나오는 index를 반환한다.

0, 1, 2, 3, 4, 5, 6 번째 값이 4 이렇게 말입니다.

그래서 6을 반환합니다.

 

이해했어요 저는

 

근데 이 함수들은 꼭 정렬된 배열에서만 사용해야 합니다.

이유는 정렬되지 않은 배열을 기반으로 사용하게 되면 예상하지 못한 결과가 나올수도 있습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

int main()
{
    vector<int> vec { 1, 2, 3, 3, 3, 4 };
    cout << lower_bound(a.begin(), vec.end(), 3) - vec.begin() << '\n';		// 2
    cout << upper_bound(a.begin(), vec.end(), 3) - vec.begin() << '\n';		// 5
}

 

위의 코드와 결과값처럼 숫자 3을 찾을 때 lower_bound()는 2, upper_bound()는 5를 반환합니다.

3이 시작되는 최소점은 lower_bound(), 3을 초과하는 시점은 upper_bound()로 찾을 수 있어요.

 

근데 왜 vec.begin()을 왜 빼는건지 생각해봅시다.

 

lower_bound(), upper_bound()는 해당 자료에서 이터레이터(한 개체의 주소)를 반환하는데

이것을 에스터리스크를 통해서 값을 확인할 수 있습니다.

그러면 lower_bound(vec.begin(), vec.end(), 3))는 3이나옵니다.

말 그대로 시작되는 최소점의 값을 나타내죠

그렇다면 이 시작점의 몇번째인지 나타내려면 확인해보면 알 수 있습니다.

vec[0] = 1

vec[1] = 2

vec[2] = 3

vec[3] = 3

...

...

..

 

이런식인데 그렇다면 최소점의 3은 0, 1, 2번째의 값입니다.

그렇기에 vec.begin()은 1이기때문에 3 - 1 = 2 이런식으로 몇 번째인지 구할 수 있습니다.

 

vec.begin()은 그럼 왜 빼는 걸까요?

lower_bound()나 upper_bound()는 해당 자료형으로부터 이터레이터를 반환하는데, 몇 번째인지 추려내려면 이터레이터에서 begin()을 빼주어야 합니다.

 

그러면 lower_bound()로 나오는 이터레이터가 어떤 값이 나올까요?

확인해봅시다.

 

근데 바로 확인이 안되며 &*(값에서 주소를 확인)를 통해 확인할 수 있습니다.

이유는 이터레이터는 저번 포스팅처럼 말했듯이 컨테이너의 한 주소를 가리키는 개체라고 했습니다.

그러면 에스터리스크를 통해 값을 확인하고 그 값의 주소를 확인할 수 있기 때문이죠.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec { 1, 2, 3, 3, 3, 4 };
    cout << &*lower_bound(vec.begin(), vec.end(), 3) << '\n';
    cout << &*vec.begin() << '\n';
    cout << &*(vec.begin() + 1) << '\n';
    
    return 0;
}

 

이것을 실행해보면

 

 

이러한 값들이 나오는데 

그림으로 확인해봅시다.

이렇게 보면 좀 설명하기 쉬울 것 같아서 그려봤습니다.

결국 우리가 lower_bound를 통해서 가져온 이터레이터는 0x000001E5318E2448입니다.

여기서 주소값끼리 -(마이너스)하게되면 즉 0x000001E5318E2448에서 vec.begin() = 0x000001E5318E2440을 빼면 해당주소값에서 몇 번째에 이 요소가 들어있는지 알 수 있게 됩니다.

 

일명의 꼼수죠

 

또한 이를 사용해서 lower_bound가 가리키는 요소가 뭔지 확실히 알 수 있습니다.

 

#include <iosteream>
#include <vector>

tpyedef long long ll;

int main()
{
    vector<int> vec { 1, 2, 3, 4, 100 };

    cout << *lower_bound(vec.begin(), vec.end(), 100) << '\n';
    
    return 0;
}

 

이러면 결과값은 100이 나오게 됩니다.

당연히 lower_bound를 통해 100을 찾는 최소지점은 그 주소를 반환하게 되고 그 주소를 에스터리스크를 통해 값을 얻어오면 100이 나오는 게 맞죠

 

응용 한 번 해봅시다.

이 vector에 3이 몇개 있는지도 체크해볼 수 있습니다.

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec { 1, 2, 3, 3, 3, 3, 4, 4,};
    
    cout << upper_bound(vec.begin(), vec.end(), 3) - lower_bound(vec.begin(), vec.end(), 3) << '\n';
    
    return 0;
}

upper_bound를 통해 3보다 큰 값이 처음인 부분 즉 4의 첫번 째 이터레이터를 반환합니다.

거기서 lower_bound를 통해 3이 시작되는 최소점의 이터레이터를 반환합니다.

그렇다면 그 둘을 빼면 몇개인지 값이 나오겠죠?

 

만약에 없는 값을 입력하면 어떻게 될까요?

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> vec;
    
    for (int i = 2; i <= 5; ++i)
        vec.push_back(i);
    vec.push_back(7);
    
    cout << upper_bound(vec.begin(), vec.end(), 6) - vec.begin() << '\n';
    
    cout << lower_bound(vec.begin(), vec.end(), 6) - vec.begin() << '\n';
    
    cout << upper_bound(vec.begin(), vec.end(), 9) - vec.begin() << '\n';
    
    cout << lower_bound(vec.begin(), vec.end(), 9) - vec.begin() << '\n';
    
}

 

엥,?

뭘까요 이게

무언가 눈치채분들도 있을겁니다!

 

맞아요 그 근방을 반환합니다!

 

처음은 여거였습니다.

 

    cout << upper_bound(vec.begin(), vec.end(), 6) - vec.begin() << '\n';

 

2, 3, 4, 5, 7에서 6보다 큰값은?

7이긴한데 6보다 작으니 5의 이터레이터를 반환해 4를 반환하게 됩니다.

 

    cout << lower_bound(vec.begin(), vec.end(), 6) - vec.begin() << '\n';

그렇다면 여거는 어떻게 해석할까요?

6이나올 최소의 시작점을 반환해야 하는데 6이 없으니 그 근방인 5의 이터레이터를 반환해

4번째라는 것을 반환합니다.

 

이해 가셨나요?

나머지도 더 해석해보죠

    cout << upper_bound(vec.begin(), vec.end(), 9) - vec.begin() << '\n';

9보다 큰 값의 첫번째의 이터레이터를 반환하는 upper_bound 근데 우리가 가지고 있는 컨테이너의 데이터는 2, 3, 4, 5, 7에서는 9가 없으니 그 근방인 7의 이터레이터를 반환하고 5번째라는 값이 나온다.

 

    cout << lower_bound(vec.begin(), vec.end(), 9) - vec.begin() << '\n';

이 또한 마찬가지 9가 시작되는 최소점이 없으니 그 근방인 7의 이터레이터를 반환하고 5번째라는 값이 나온다.

 

후 회사 갔다오고 다시 이어서 쓰려니 복습하는데 좀 걸렸네요

 

내일 주말이다 헿

 

 

끝!