[탐색] Lower Bound와 Upper Bound

Lower Bound와 Upper Bound

• 일종의 이분 탐색(binary search)
• 오름차순으로 정렬되어 있을 때를 가정한다.

 

Lower Bound

-정렬된 숫자들 중에 목표값이 처음 등장하는 인덱스 값을 반환한다.

int lower_bound(int *arr, int key, int size) {
    int mid, left, right;
    left = 0;
    right = size - 1;
    
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] >= key)
            right = mid;
        else
            left = mid + 1;
    }
    return right;
}

 

 

Upper Bound

-정렬된 숫자들 중에 목표값보다 높은 숫자가 처음 등장하는 인덱스 값을 반환한다.

int upper_bound(int*arr, int key, int size) {
    int mid, left, right;
    left = 0, right = size - 1;
 
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] > key)
            right = mid;
        else left = mid + 1;
    }
    return right;
}

 

 

전체 코드

-목표값이 숫자 2일 때, lower bound와 upper bound의 결과

#include <stdio.h>
 
int lower_bound(int *arr, int key, int size) {
    int mid, left, right;
    left = 0;
    right = size - 1;
    
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] >= key)
            right = mid;
        else
            left = mid + 1;
    }
    return right;
}
 
int upper_bound(int*arr, int key, int size) {
    int mid, left, right;
    left = 0, right = size - 1;
 
    while (left < right) {
        mid = (left + right) / 2;
        if (arr[mid] > key)
            right = mid;
        else left = mid + 1;
    }
    return right;
}
 
int main() {
    int arr[] = { 1,2,2,2,3,3,5,7,7,7,7,9,11 };
    printf("%d\n", lower_bound(arr, 2, sizeof(arr) / sizeof(arr[0])));
    printf("%d\n", upper_bound(arr, 2, sizeof(arr) / sizeof(arr[0])));
    return 0;
}

 

[출력결과]

 

 

+) C++의 STL을 활용한 lower과 upper

-배열과 iterator 사용 가능

 

배열일 경우(주소 값으로 계산)

• std::lower_bound(arr, arr+n, key) - arr
• std::upper_bound(arr, arr+n, key) - arr

목표값이 숫자 2일 때, lower_bound와 upper_bound의 결과

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int arr[] = { 1,2,2,2,3,3,5,7,7,7,7,9,11 };
    int lower = lower_bound(arr, arr + 13, 2) - arr;
    int upper = upper_bound(arr, arr + 13, 2) - arr;
 
    printf("%d %d\n", lower, upper);
    return 0;
}

 

[출력결과]