백준 1920번 : 수 찾기

문제 링크 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 문제 설명 

 

n개의 정수가 주어지고 그다음 m개의 정수가 주어지는데

m개의 정수가 순서대로 n개의 정수중에 포함 되있으면 1 아니면 0출력 하면된다 . 줄바꿈 출력 주의.

 

알고 리즘

 

이분탐색으로 찾으면됨 .

먼저 n개의 정수를 정렬한뒤

lo = 0 , hi = n-1 로 지정하고 while문으로 이분탐색진행 하면된다.

 

 코드 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int N, M;
    int arr[100001];
 
 
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
 
    sort(arr, arr + N);
    cin >> M;
    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        int lo = 0;
        int hi = N - 1;
        bool pos = false;
 
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
 
            if (num == arr[mid]) {
                pos = true;
                cout << 1;
                break;
            }
            else if (num < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
 
        }
        if (!pos) cout << 0;
        cout << "\n";
 
    }
 
    return 0;
 
 
}