백준 01920 - 수 찾기

출처 : https://www.acmicpc.net/problem/1920 

1920번: 수 찾기

 

고려사항

• 이분 탐색.
• 모든 수를 벡터에 담아서 알고리즘 헤더에 있는 sort 함수를 사용한다.
  sort 함수가 퀵소트 기반으로 구현되어 있으니 정렬이 빠르게 된다!
• 수가 있는지를 판별할 때에는 정렬된 벡터에서 이분탐색을 실시!

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int search(vector<int> &v, int target){
    int left = 0;
    int right = v.size();
    int mid;

    while(left <= right){
        mid = (left + right) / 2;

        if(v[mid] == target){
            return 1;
        }

        if(v[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return 0;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    vector<int> v;
    int n, m, tmp;

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

    sort(v.begin(), v.end());
    cin>>m;
    for(int i=0;i<m;++i){
        cin>>tmp;
        cout<<search(v, tmp)<<"\n";
    }

    return 0;
}