<개인공부>/[Algorithm]

[탐색] lower_bound, upper_bound

사용자 BlockDMask 2017. 10. 11. 09:00
반응형

안녕하세요. BlockDMask 입니다.

오늘은  이진탐색과 유사하나 조금 다른 

lower_boundupper_bound에 대해 알아보겠습니다.

1. lower_bound

  • lower_bound 란?
    - 이진탐색(Binary Search)기반의 탐색 방법입니다. (배열 또는 리스트가 정렬 되어있어야 한다.)
    - lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾습니다.
    - 같은 원소가 여러개 있어도 상관 없으며, 항상 유일한 해를 구할 수 있습니다.
    - 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면,
    arr[mid-1] < key 이면서 arr[mid] >= key 인 최소의 m 값을 찾으면 됩니다. (m>=2)


  • 직접 구현한 lower_bound 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    //lower_bound
    //n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
     
    #include<iostream>
    using namespace std;
     
    int mylower_bound(int * arr, int n, int key){
        int start = 0;
        int end = n;
     
        int mid = n;
        while(end - start >0){  //start 가 end 와 같지 않고, 넘지 않을 때
            mid = (start+end)/2;    //중앙 index
     
            if(arr[mid] < key){ //key 값이 중앙 값보다 크면
                start = mid + 1;//mid 보다 오른쪽으로
            }else{  //key 값이 중앙값보다 작거나 같으면
                end = mid;  //mid 포함 왼쪽 (포함하는 이유는 key값과 같은게 없을 때 큰수중 가장 작은값을 위해)
            }
     
        }
        return end+ 1;
    }
     
    int main(void){
        int arr[10= {1245667779};
     
        cout << "lower_bound(6) : " << mylower_bound(arr, 106<< endl;
        cout << "lower_bound(7) : " << mylower_bound(arr, 107<< endl;
        cout << "lower_bound(8) : " << mylower_bound(arr, 108<< endl;
        cout << "lower_bound(9) : " << mylower_bound(arr, 109<< endl;
        return 0;
    }
    cs


  • STL 에서 제공하는 lower_bound 사용.

    STL에 따르면 lower_bound는 이렇게 선언 되어있습니다.

    template <class ForwardIterator, class T>
    ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

    - lower_bound(arr, arr+n, key); //이런식으로 사용.

    반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
    배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다. 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //lower_bound
    //n개로 이루어진 정수 집합에서 원하는 수 k 이상인 수가 처음으로 등장하는 위치를 찾으시오
     
    #include<iostream>
    #include<algorithm> //헤더파일
    using namespace std;
     
    int main(void){
        int arr[10= {1245667779};
     
        cout << "lower_bound(6) : " << lower_bound(arr, arr + 106- arr + 1<< endl;
        cout << "lower_bound(7) : " << lower_bound(arr, arr + 107- arr + 1<< endl;
        cout << "lower_bound(8) : " << lower_bound(arr, arr + 108- arr + 1<< endl;
        cout << "lower_bound(9) : " << lower_bound(arr, arr + 109- arr + 1<< endl;
        return 0;
    }
    cs
  • 출력 결과 

    두가지 경우 모두 동일한 출력이 나옵니다.



2. upper_bound

  • upper_bound 란?
    - lower_bound와 마찬가지로 이진탐색(Binary Search)기반의 탐색법 입니다.
    - 이진탐색(Binary Search)기반이므로 배열이나 리스트가 오름차순으로 정렬 되어있어야 합니다.
    - upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
    - 같은 원소가 여러개 존재 해도 항상 유일한 해를 구할 수 있습니다.
    - 구간이 [start, end]인 배열이 있을때, 중간위치의 index를 mid 라고 하면, 
    arr[mid-1] <= key 이면서 arr[mid] > key 인 최소의 m 값을 찾으면 됩니다. (m>=2)
    - upper_bound에서 기억해야 할 것은 (같은 값이 아닌) key 값을 초과하는 가장 첫번째 원소의 위치 라는 것 입니다.

  • 직접 구현한 upper_bound 함수

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    //upper_bound
    //n개로 이루어진 정수 집합에서 원하는 수 k 보다 큰 수가 처음으로 등장하는 위치를 찾으시오
     
    #include<iostream>
    using namespace std;
     
    int myupper_bound(int *arr, int n, int key){
        int start = 0;
        int end = n;
        int mid;
     
        while(end - start > 0){
            mid = (start+end)/2;
     
            if(arr[mid] <= key){    //lower_bound와 다른 점은 여기 '=' 하나
                start = mid + 1;
            }else{
                end = mid;
            }
     
        }
     
        return end +1;
    }
     
    int main(void){
        int arr[10= {1245667779};
     
        cout << "upper_bound(6) : " << myupper_bound(arr, 106)<< endl;
        cout << "upper_bound(7) : " << myupper_bound(arr, 107)<< endl;
        cout << "upper_bound(8) : " << myupper_bound(arr, 108)<< endl;
        cout << "upper_bound(9) : " << myupper_bound(arr, 109)<< endl;
        return 0;
    }
    cs



  • STL 에서 제공하는 lower_bound 사용.

    STL에 따르면 upper_bound는 이렇게 선언 되어있습니다.


    template <class ForwardIterator, class T>
    ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

    - upper_bound(arr, arr+n, key); //이런식으로 사용. (lower_bound와 사용법은 같습니다)

    반환형이 Iterator 이므로 vector container인 경우에는 iterator에서 v.begin()을 뺀 값으로 몇 번째 인자인지 계산을 하고,
    배열인 경우에는 배열의 첫번째 주소를 가리키는 배열의 이름을 빼면 몇 번째 인자인지 알 수 있습니다. 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //upper_bound
    //n개로 이루어진 정수 집합에서 원하는 수 k 보다 큰 수가 처음으로 등장하는 위치를 찾으시오
     
    #include<iostream>
    #include<algorithm> //헤더파일
    using namespace std;
     
    int main(void){
        int arr[10= {1245667779};
     
        cout << "upper_bound(6) : " << upper_bound(arr, arr + 106- arr + 1<< endl;
        cout << "upper_bound(7) : " << upper_bound(arr, arr + 107- arr + 1<< endl;
        cout << "upper_bound(8) : " << upper_bound(arr, arr + 108- arr + 1<< endl;
        cout << "upper_bound(9) : " << upper_bound(arr, arr + 109- arr + 1<< endl;
        return 0;
    }
    cs

  • 출력 결과

<출처>

http://www.cplusplus.com/reference/algorithm/upper_bound/

http://www.cplusplus.com/reference/algorithm/lower_bound/

반응형