백준_1920 : 수 찾기 - C++

문제

---

문제 해석

- 정답 수열이 존재 하고, 입력 수열이 존재 한다고 가정 한다.

- 이때 입력 수열의 수들이 정답 수열에 존재 하는지를 알아내는 문제이다.

---

알고리즘

- 먼저 주어지는 정답 수열을 sorting 한다.

- 이 후 입력 수열의 수가 들어 올 때 마다 정답 수열에서 이진 탐색으로 탐색 해 주면 된다.

- 이 때 수가 정답 수열에 존재 하면 1을 존재 하지 않으면 0을 출력해 주면 된다.

---

코드

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

long N, M;
long A[100001];

void b_search(long tmp){
    long low = 0, high = N-1, mid;

    while(low <= high){
        mid = (high + low) / 2;
        if(tmp == A[mid]){
            printf("1\n");
            return;
        } else if(tmp < A[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    printf("0\n");
    return;
}

int main(){
    scanf("%ld", &N);
    for(long i = 0; i < N; i++){
        scanf("%ld", &A[i]);
    }

    sort(A, A+N);

    scanf("%ld", &M);
    for(long i = 0; i < M; i++){
        long tmp; 
        scanf("%ld", &tmp);
        b_search(tmp);
    }

    return 0;
}