Lower bound Upper bound

Lower bound

선형구조의 부분탐색인 이진탐색은 찾고자 하는 값이 없으면 실패한다.

하지만, Lower bound는 찾고자 하는 값보다 이상인 값이 처음 나타나는 위치이다, 

Lower bound는 같은 원소가 여러개 있어도 상관 없다.

위치를 찾기위해, 이진탐색에서 조금만 바꾸면 된다.

#include <stdio.h>
 
int find(int arr[], int f, int s, int e);
 
int main(void)
{
    int i;
    int f;
    int n;
    int arr[10000] = {};
    int check = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", arr + i);
    }
    scanf("%d", &f);
    printf("%d\n", find(arr, f, 0, n));
    
}
int find(int arr[], int f, int s, int e)
{
    int m;
    while (e - s > 0)
    {
        m = (s + e) / 2;
        if (arr[m] < f)
        {
            s = m + 1;
        }
        else
            e = m;
    }
    return e + 1;
}

n 개의 원소를 입력했을때, 입력한 값 이상의 위치가 처음으로 나타나는 곳을 반환하는 코드이다.

s와 e 가 탐색 범위이다, 

이진 탐색이 기반이기에, m 이 사용되어, 범위의 /2 만큼의 값을 갖는데,

arr[m] 이 f 보다 크면, s 가 m + 1 이되고, 아니면, e 가 m 이 된다.

그런식으로 범위를 줄여나가면, 언젠간 멈추는 경우가 생기는데, 그때가 찾는 경우이다.

인덱스가 0부터 시작하므로, +1 의 값을 반환한다.

Upper bound

upper bound 는 lower bound 와 달리, 입력한 값이 초과하는 위치를 출력하는 알고리즘이다.

 
#include <stdio.h>
 
int find(int arr[], int f, int s, int e);
 
int main(void)
{
    int i;
    int f;
    int n;
    int arr[10000] = {};
    int check = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", arr + i);
    }
    scanf("%d", &f);
    printf("%d\n", find(arr, f, 0, n));
    
}
int find(int arr[], int f, int s, int e)
{
    int m;
    while (e - s > 0)
    {
        m = (s + e) / 2;
        if (arr[m] <= f)
        {
            s = m + 1;
        }
        else
            e = m;
    }
    return e + 1;
}

Lower bound 에서 썻던 코드와 다른점은 arr[m] < f 이 arr[m] <= f 로 바뀌엇 단 점이다.

이렇게 되면 만약 5, 1 3 3 5 7 , 5 를 입력했을때,

arr[2] < = 5 이므로, 

s 가 3이 된다, 이런식으로 범위를 늘려가다가, 

arr[4] <= 5 가 성립하지 않으므로, 초과하는건 5번째이다.