[백준] 1920번 수 찾기 c++

문제

 

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보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

문제접근 및 풀이

1. 배열 A를 오름차순으로 sort 한 후

2. M개의 각 정수에 대해 A배열에 존재하는 지 여부를 이분탐색을 이용해 찾는 방식이다.

1번에서 정렬 시 nlogn, 2번 탐색시 m개의 원소에 대해 이분탐색(logm)이 사용된다.

 

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

using namespace std;

int n,m;
vector<int> a,b;

int find(int key){
    int mid=0;
    int start = 0;
    int end = a.size()-1;
    
    while(end - start >= 0){
        mid = (start+end) / 2;
        if(key == a[mid]) return 1;
        if(key > a[mid]) start = mid + 1;
        if(key < a[mid]) end = mid - 1;
    }
    return 0;
}

int main()
{
    
    scanf("%d", &n);
    for(int x,i=0; i<n; i++){
        scanf("%d", &x);
        a.push_back(x);
    }
    scanf("%d", &m);
    for(int x,i=0; i<m; i++){
        scanf("%d", &x);
        b.push_back(x);
    }
    
    sort(a.begin(), a.end());
    
    for(int i=0; i<b.size(); i++){
        if(find(b[i])){
            printf("1\n");
        }else{
            printf("0\n");
        }
    }
    

    return 0;
}