[Algorithm][Template] 이진 탐색, 파라메트릭 서치

이진탐색을 사용하기 위한 조건 : 정렬되어 있어야 한다.

찾으려는 데이터와 중간점(middle)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.

시간 복잡도 : O(log(N))

 

1) 재귀를 이용한 구현

#include <iostream>
#include <vector>

using namespace std;

int n, target;
vector<int> v;

int binarySearch(int s, int e, int t) {
    if (s > e)
        return -1;

    int mid = (s + e) / 2;
    if (v[mid] == t) {
        return mid;
    }
    else if (v[mid] < t) {
        return binarySearch(mid+1, e, t);
    }
    else {
        return binarySearch(s, mid-1, t);
    }
}

int main(void) {
    cin >> n >> target;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    cout << binarySearch(0, n-1, target) + 1 << "\n";

    return 0 ;
}

2) while문을 이용한 구현

#include <iostream>
#include <vector>

using namespace std;

int n, target;
vector<int> v;

int binarySearch(int t) {
    int s = 0;
    int e = v.size() - 1;

    while (s <= e) {
        int mid = (s + e) / 2;
        if (v[mid] == t) {
            return mid;
        }
        else if (v[mid] < t) {
            s = mid+1;
        }
        else {
            e = mid - 1;
        }
    }

    return - 1;
}
int main(void) {
    cin >> n >> target;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    cout << binarySearch(target) + 1 << "\n";

    return 0 ;
}

나의 경우 2번이 편하다.

1번, 2번 아무거나 사용하여도 상관 없다!

 

파라메트릭 서치(Parametric Search)

• 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제(decision problem)로 바꾸어 해결하는 기법
• 예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이분 탐색으로 결정 문제를 해결하면서 범위를 좁혀갈 수 있다.

Lower Bound, Upper Bound

• 이진 탐색으로 돌음
• countByRange 처럼 정렬된 배열에서 a~b까지의 숫자의 개수를 O(logN)으로 찾고자 할때 주로 사용한다.

Lower Bound

• 키값보다 크거나 같은 첫번째 값
• 찾으려고 하는 key 값이 없으면, key 값 초과인 값들 중, 가장 작은 값
  
  

Upper Bound

• 키값보다 큰 첫번째 값
• 최댓값보다 더 큰 값을 찾고자 하는 경우에는, 마지막 요소 다음 메모리를 가리키는 iterator(end()와 같은)를 반환한다. 따라서, 이 iterator에 접근하면 쓰레기값을 반환.

직접 구현할 경우는 기존 이진 탐색에서 값을 찾았을 경우 left를 이동할지 right를 이동할지를 생각해 로직을 수정하면된다.

또한 증명하는 방법은 이진탐색은  l~r의 크기가 1 또는 2일 경우를 결국은 지나므로 해당하는 경우를 모두생각해보면 편하다.

 

1) 직접 구현

#include <iostream>
#include <vector>

using namespace std;

int n, key;
vector<int> v;

// Key 보다 크거나 같은 첫번째 값 반환
int lowerBound() {
    int l = 0, r = n-1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (v[mid] < key) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    return l;
}

// Key보다 큰 첫번째 값
int upperBound() {
    int l = 0, r = n-1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if ( v[mid] <= key) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    return l;
}

// 값이 [left, right]인 데이터의 개수를 반환하는 함수
int countByRange() {
    int left = lowerBound();
    int right = upperBound();

    return right - left;
}

int main(void) {
    cin >> n >> key;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    int cnt = countByRange();
    if (cnt == 0) {
        cout << -1 << "\n";
    }
    else {
        cout << cnt << "\n";
    }

    return 0 ;
}

2) STL

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, key;
vector<int> v;

// 값이 [left, right]인 데이터의 개수를 반환하는 함수
int countByRange() {
    // Key 보다 크거나 같은 첫번째 값 반환
    vector<int>::iterator left = lower_bound(v.begin(), v.end(), key);
    // Key보다 큰 첫번째 값
    vector<int>::iterator right = upper_bound(v.begin(), v.end(), key);

    return right - left;
}

int main(void) {
    cin >> n >> key;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        v.push_back(t);
    }

    int cnt = countByRange();
    if (cnt == 0) {
        cout << -1 << "\n"; 
    }
    else {
        cout << cnt << "\n";
    }

    return 0 ;
}