[탐색 알고리즘] lower_bound, upper_bound

[탐색 알고리즘] lower_bound, upper_bound

lower_bound, upper_bound는 기본적으로 이진 탐색을 기반으로 하기 때문에 탐색하고자 하는 수열(원소들)이 오름차순으로 정렬되어 있어야 합니다. 이렇게 정렬된 리스트에서 특정 값 위치를 찾을 때 사용합니다. 그렇다면 특정 값이 무엇인지 밑에 설명을 보시면 알 수 있습니다.

 

 

1. lower_bound :   크거나 같은 수 중에서 첫 번째 수 (특정값)

 

2에 대한 lower_bound 즉 , 2와 같거나 큰 수중 가장 작은 인덱스를 찾고자 한다면 그림에서 보이는 바와 같이 1번 째입니다. 

 

 

 

[소스 코드]

 

#include <iostream>
using namespace std;
const int N = 8;
int arr[N] = { 1, 2, 2, 2, 3, 3, 5, 6 };
int lower_bound(int num) {
    int left = 0, right = N - 1;
    int ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == num) {
            ans = mid;
            right = mid - 1;
        }
        else if (arr[mid] > num) right = mid - 1;
        else left = mid + 1;
    }
    return ans;
}
int main() {
    cout << "2에 대한 Lower_bound : " << lower_bound(2) << '\n';
    return 0;
}

 

 

2. upper_bound : 큰 수 중 첫 번째 수 (특정값)

 

2에 대한 upper_bound 즉, 2보다 큰 수 ( 같은 수 포함x ) 인 3의 index는 4번째입니다.

 

 

[소스 코드]

#include <iostream>
using namespace std;
const int N = 8;
int arr[N] = { 1, 2, 2, 2, 3, 3, 5, 6 };
int upper_bound(int num) {
    int left = 0, right = N - 1;
    int ans = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == num) {
            ans = mid + 1;
            left = mid + 1;
        }
        else if (arr[mid] > num) right = mid - 1;
        else left = mid + 1;
    }
    return ans;
}
int main() {
    cout << "2에 대한 Upper_bound : " << upper_bound(2) << '\n';
    return 0;
}