백준 10815번 - 숫자 카드

https://www.acmicpc.net/problem/10815

N개의 카드가 있을 때

주어진 번호가 있는지 확인해야 한다.

이 문제를 이분 탐색으로 풀지않는다면

음수까지 고려해 M*2만큼 배열의 크기를 잡고 인덱스로 바로 접근을 해야한다.

따라서 정렬을 한 뒤에

로그N의 시간만큼 탐색을 진행하여 문제를 해결하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,M;
vector<int> card;
int binarySearch(int key){
    int first=0;
    int last=card.size()-1;
    int middle=(first+last)/2;
    
    while(first<=last){
        if(card[middle]==key)
            return 1;
        
        if(card[middle]>key)
            last=middle-1;
        
        if(card[middle]<key)
            first=middle+1;
        
        middle=(first+last)/2;
        
    }
    
    return 0;
}
int main() {
    
    std::ios_base::sync_with_stdio(false);
    cin>>N;
    
    card=vector<int> (N,0);
    for(int i=0;i<N;i++)
        cin>>card[i];
    
    cin>>M;
    vector<int> vec(M,0);
    for(int i=0;i<M;i++)
        cin>>vec[i];
    
    sort(card.begin(),card.end());
    
    for(int i=0;i<M;i++){
        cout<<binarySearch(vec[i])<<" ";
    }
    
    
    
    return 0;
}