2. 이분 탐색 (Binary search)

이분탐색 (Binary search)

이분탐색은 결과적으로 나오는 index의 값을 기준으로 upper_bound와 lower_bound로 나뉜다.

 

단,이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다.

일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다. 반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약, compare한 값과 같을때는 그 값을 출력하면 된다.

 

그런데 중복되는 수가 존재하는 경우에는 이분탐색을 설정하는 방법에 따라서 출력되는 방법이 달라지게 된다.설정하는 방법은 총 2가지가 존재하는데, Upper_bound와 Lower_bound이다.

1. Upper_bound

위 방식은 compare할 숫자를 기준으로 자기보다 큰 최소의 값을 가지는 index를 출력시킨다.
중간값이 compare_value와 작은 경우에는 당연하게 start를 mid + 1로 옮기지만, 같은 값이 나와도 mid + 1로 옮김으로써 , 수렴값을 compare_value를 가지는 최대 index에서 1칸보다 큰 값으로 수렴시킨다.

 

즉, 결과적으로 마지막 compare_value를 가지는 값의 다음 값까지 start지점이 옮겨지게 되고, 결과적으로 start값과 end는 같아진다.
왜냐하면, 중간값이 compare_value보다 작거나 같은 순간 계속해서 판단하는 scope가 한칸씩 뒤로 밀린다. 더 큰 경우에는 계속해서 scope가 앞쪽으로 좁아지게 된다. 에초에 mid값은 계속해서 작아지게 되기에 end값이 계속해서 앞쪽으로 밀리기 때문이다. 그래서 굳이 mid - 1로 하지 않아도 무방하다.

 

다만, end값을 반드시 초기 vector의 크기로 해야한다.
왜냐하면 끝의 값이 compare_value인 경우에는 마지막 index가 튀어나오게 되어 예외케이스가 발생하기 때문이다.

// Upper_bound (이분탐색에서의 상계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;

    if(card[mid] <= compare_value){
        start = mid + 1;
    }

    else{
        end = mid;
    }
}

2. Lower_bound

위 방식은 Upper_bound와 기본적으로 방법은 거의 유사하나, compare할 숫자를 기준으로 compare와 같거나 큰 수를 갖는 index의 최솟값을 출력시킨다.

 

중간값이 compare_value와 크거나 같은 경우에는 end를 mid로 옮김으로써 scope는 뒤쪽부분이 앞쪽으로 좁아지게 된다. 작은 경우에는 start가 mid + 1로 옮김으로써 scope가 한칸씩 앞으로 이동하게 된다. 따라서 결과적으로 수렴값을 compare_value를 가지는 index의 최솟값으로 수렴시킨다.

 

즉, 결과적으로 마지막 compare_value를 가지는 값의 최초의 값으로 start지점이 옮겨지게 되고, 결과적으로 start값과 end는 같아진다.
왜냐하면, 중간값이 compare_value보다 작으면 계속해서 판단하는 scope가 한칸씩 뒤로 밀린다. 더 크거나 같은 경우에는 계속해서 scope가 앞쪽으로 좁아지게 된다. 에초에 mid값은 계속해서 작아지게 되기에 end값이 계속해서 앞쪽으로 밀리기 때문이다. 그래서 굳이 mid - 1로 하지 않아도 무방하다.

 

이 경우에도 반드시 end를 벡터의 사이즈로 잡아야 한다. 그래야 존재하지 않는 경우 end값이 size를 지칭하면서 끝나게 된다. 즉 Lower_bound는 compare를 기준으로 같거나 큰 수를 가지는 index 중 최솟값이므로 compare가 query의 어떤 수보다도 더 큰 경우에는 vector의 size가 return되게 된다.

// Lower_bound (이분탐색에서의 하계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;

    if(card[mid] < compare_value){
        start = mid + 1;
    }

    else{
        end = mid;
    }
}

주먹구구식으로 처리하지 말고, 동일한 방식으로 짜도록 노력해야 한다.

 

만약, 중복되는 케이스가 없는 일반적인 케이스에서는 직관적으로 훨씬 이해가 쉬운 lower_bound 방식을 활용해서 처리해 주면 된다.

이분탐색의 Time complexity는 O(log2(n))이다.

 

매우 자주 사용되는 알고리즘이므로 잘 기억해 두어야 한다.

(보통 일반적으로 정렬과 함께 사용된다.)

 

다만, Upper_bound나 Lower_bound의 경우 compare와 같은 숫자가 반드시 존재한다는 전제면 end값을 가질 수 있는 index값으로 설정해도 무방하다.(어차피 안되는 경우가 compare가 해당 query의 어떤 숫자보다 더 큰 경우에 발생하므로)

이 알고리즘을 활용한 문제는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;
    vector<int> card;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        card.push_back(temp);
    } // store data

    sort(card.begin(), card.end()); // sorting data

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int check_value;
        cin >> check_value;
        int start = 0;
        int end = n;
        int mid = -1;
        int min, max;

        // Upper bound
        while (start < end){
            mid = (start + end) / 2;
            if(card[mid] <= check_value){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }

        max = start;

        start = 0;
        end = n;

        // Lower bound
        while (start < end){
            mid = (start + end) / 2;
            if(card[mid] < check_value){
                start = mid + 1;
            }
            else{
                end = mid;
            }
        }
        min = start;

        cout << max - min<< " ";
    }

    cout << "\n";

    return 0;

}