[중급-2] Lower bound, Upper bound

학습 목표 :

Lower bound의 개념과 방법을 이해한다.

Upper bound의 개념과 방법을 이해한다.

1. Lower bound

->Lower bound

lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치.

원소가 여러개 있어도 상관 무.

즉, 찾고자 하는 값 이상이 처음 나타나는 위치를 찾기 위해 쓴다.(이분탐색 방법 조금 변형하면 된다)

문제 : n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어있으며, 같은 수가 여러 개 존재할 수 있다.

입력 : 

첫줄에 한 정수 n이 입력됨.

둘째 줄에 n개의 정수가 공백으로 구분되어 입력됨.

셋째 줄에 찾고자 하는 값 k가 입력됨.

2<=n<=1,000,000  ,  각 원소의 크기<100,000,000

출력 : 

찾고자 하는 원소의 위치 출력. 만약 모든 원소가 k보다 작으면 n+1을 출력.

팁 : 찾아야할 데이터 k와 같거나 큰 가장 첫 위치 lower bound, 탐색 구간의 시작위치와 마지막 위치는 각각 0과 8(7+1)이다. 중간위치는 4이다. 왜 마지막 위치가 8이냐면, 만약 모든 원소가 찾아야 할 값보다 큰경우, n+1을 출력하기 때문이다. 그리고 이분탐색을 이용한다.

핵심 코드 : 

int solve(int s, int e){
    int m;
    while(e-s>0){
        m=(s+e)/2;
        if(A[m]<k)
            s=m+1;
        else
            e=m;
    }
    return e+1;
}

stdlib.h에 있는 함수 : std::lower_bound(A, A+n, k, [compare]) ==> 어떤 위치가 나오는데 여기서 -A+1을 하면 배열에서의 상대적 값(우리가 원하던 값)이 정상적으로 나온다.

->Upper bound

:찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치이다.

lower bound와 굉장히 흡사하다.

문제 : n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어있으며, 같은 수가 여러 개 존재할 수 있다.

입력 : 

첫줄에 한 정수 n이 입력됨.

둘째 줄에 n개의 정수가 공백으로 구분되어 입력됨.

셋째 줄에 찾고자 하는 값 k가 입력됨.

2<=n<=1,000,000  ,  각 원소의 크기<100,000,000

출력 : 

찾고자 하는 원소의 위치 출력. 만약 모든 원소가 k보다 작으면 n+1을 출력.

핵심코드 : 

int solve(int s, int e){
    int m;
    while(e-s>0){
        m=(s+e)/2;
        if(A[m]<=k)
            s=m+1;
        else
            e=m;
    }
    return e+1;
}

stdlib.h에 있는 함수 : std::upper_bound(A, A+r, k, [compare])  ==>compare이 생략되면 기본적으로 오름차순으로 정렬한 상태라고 가정함.