[삼성역량테스트PRO] Binary Search

 

 

 

 

역량테스트 Pro 에만 나오는 개념이라서 여기에 포스팅한건 아니다

 

물론 자료구조시간에, A형 공부를 하면서도 배운 내용이지만 정리하지 않아서 해본다.

 

---

 

정의

 

정렬되어 있는 배열에서 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

 

시간복잡도는 O(logN) 이다.

 

 

---

 

활용

 

STL을 사용할 경우 algorithm 헤더의 binary_search, lower_bound, upper_bound를 사용할 수 있다.

 

이들은 오름차순 정렬되어있는 배열, vector에서만 정상작동한다.

 

아래 문제에서 활용해보자.

 

 

---

 

문제

 

백준 1920번 문제를 직접 구현을 통해 / STL을 사용한 두 가지 방법으로 풀어본다.

1920번: 수 찾기

문제 : N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 : 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 5 4 1 5 2 3 5 1 3 7 9 5 출력 : M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 1 1 0 0 1

---

1. 이분탐색 직접구현

 

#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<int>a;
int input;
int numbers;

int BinarySearch(int target, int len){
    int start = 0;
    int end = len-1;
    while(start<=end){
        int middle = (start+end)/2;
        if(a[middle]<target)
            start = middle+1;
        else if(a[middle]>target)
            end = middle-1;
        else
            return middle; // 찾았다.
    }
    return -1; // start > end 일 경우 없음 으로 종결한다.
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> input;
    for(int i=0; i<input; i++){
        cin >> numbers;
        a.push_back(numbers);
    }
    sort(a.begin(),a.end());
    int m;
    cin >> m;
    for (int i=0; i<m; i++){
        int t;
        cin >> t;
        if(BinarySearch(t,input)==-1) cout<<"0\n";
        else cout << "1\n";
    }
    return 0;
}

 

---

 

2. STL을 사용한 방법

 

<algorithm> 헤더의 binary_search 를 이용한다.

 

이 함수는 주어진 범위 내에 원소 포함 여부를 true/false로 반환해준다.

 

#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<int>a;
int input;
int numbers;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> input;
    for(int i=0; i<input; i++){
        cin >> numbers;
        a.push_back(numbers);
    }
    sort(a.begin(),a.end());
    int m;
    cin >> m;
    for (int i=1; i<=m; i++){
        int t;
        cin >> t;
        if(binary_search(a.begin(),a.end(),t)) cout<<"1\n";
        else cout << "0\n";
    }
    return 0;
}

 

 

두 방법은 완전히 동일한 시간을 소요했다.

 

끝