Algorithm - Lower bound, Upper bound (Baekjoon 10816, C)

Docs › Algorithm
, ,

  • https://jiravvit.github.io/230123-alrorithm-binsearch/

  • 위의 Binary Search에서 파생됨, 따라서 Lower Bound, Upper Bound 알고리즘은 정렬된 배열에 대해 사용이 가능함

  • Binary Search: 원하는 값 key를 찾는 과정

  • Lower bound: 원하는 값 key 이상이 처음 나오는 위치를 찾는 과정

  • Upper bound: 원하는 값 key를 초과한 값이 처음 나오는 위치를 찾는 과정

  • Binary Search는 원하는 값 key가 아니면 보통 -1을 반환함.(이 전 게시글 구현에서는 0을 반환했음.) 하지만 Lower bound와 Upper bound는 어떻게든 적절한 위치를 반환함.

Lower Bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lower_bound(int data[], int n, int key) {
    int low, high, mid;

    low = 0;
    high = n-1;

    while (low < high) {
        mid = (low+high) / 2;
        if (key <= data[mid]) 
            high = mid;
        else 
            low = mid + 1;
    }

    return high;
}

원하는 값 key 이상이면 key도 포함이다. 중복되는 key 중에서 가장 작은 인덱스를 가져온다. Binary search 코드에서 조금만 변형시켜주면 된다.

Upper Bound

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int upper_bound(int data[], int n, int key) {
    int low, high, mid;

    low = 0;
    high = n-1;

    while (low < high) {
        mid = (low+high) / 2;
        if (key < data[mid]) 
            high = mid;
        else 
            low = mid + 1;
    }

    return high;
}

low, high, mid는 모두 인덱스이다.

key보다 큰 첫 번째 위치를 찾아야 한다. key가 data[mid]보다 작으면 high를 mid로 내린다. 그럼 전체적인 인덱스는 왼쪽으로 살짝 치우친 형태일 것이다.

key가 data[mid]보다 값거나 크면 low = mid + 1을 수행한다. 쉽게 말해 mid 그 다음 인덱스를 low로 지정한다.



검정색을 먼저 읽고 빨간색을 읽으면 된다. 파란색은 참고이다.

Example (백준 10816 숫자카드 2)

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>

int n, m;

int compare(const void* a, const void* b) {
    if (*(int*)a > *(int*)b) return 1;
    else if (*(int*)a < *(int*)b) return -1;
    return 0;
}

int lower_bound(int data[], int n, int key) {
    int low, high, mid;

    low = 0;
    high = n-1;

    while (low < high) {
        mid = (low+high) / 2;
        if (key <= data[mid]) 
            high = mid;
        else 
            low = mid + 1;
    }

    return high;
}

int upper_bound(int data[], int n, int key) {
    int low, high, mid;

    low = 0;
    high = n-1;

    while (low < high) {
        mid = (low+high) / 2;
        if (key < data[mid]) 
            high = mid;
        else 
            low = mid + 1;
    }

    if (data[high] == key) 
        return high + 1;

    return high;
}


int main() {
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++)
        scanf("%d ", &arr[i]);

    qsort(arr, n, sizeof(int), compare);

    scanf("%d", &m);
    int brr[m];

    for (int i = 0; i < m; i++)
        scanf("%d ", &brr[i]);
    
    // lower_bound, upper_bound
    int lower, upper;
    for (int i = 0; i < m; i++) {
        lower = lower_bound(arr, n, brr[i]);
        upper = upper_bound(arr, n, brr[i]);
        printf("%d ", upper-lower);
    }
}

이 문제를 풀기 위해서 upper_bound 함수에서 아래 조건을 추가해줘야한다.

1
2
if (data[high] == key) 
    return high + 1;

왜냐하면.. upper_bound 함수의 반환 값은 key 값을 초과하는 첫 번째 값의 인덱스인데 key가 정렬에서 가장 큰 수라면 반환 값이 존재하지 않기 떄문이다. 그래서 n-1을 반환한다. 이 문제는 key의 개수를 알아내는 것이 목표이기 때문에 해당 경우에만 +1을 해줘야 한다. 

1
10 20 30 30 30

예시로 위의 배열에서 30의 개수는 5-2 = 3 이어야 한다.