[BOJ] 백준 1920 수 찾기

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

Approach

N, M이 작지 않은 숫자이기 때문에 배열을 한개씩 탐색하면 TLE 발생

Binary Search (이분 탐색) 

Binary Search (이분 탐색)

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int N, M, temp, x;
vector<int> vec;
 
int binarySearch(int left, int right){
    if (left > right)
        return 0;
 
    int mid = (left + right) / 2;
    if (vec[mid] == x)
        return 1;
    else if (vec[mid] > x)
        return binarySearch(left, mid - 1);
    else
        return binarySearch(mid + 1, right);
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for(int i=0; i < N; i++){
        cin >> temp;
        vec.push_back(temp);
    }
 
    sort(vec.begin(), vec.end());
 
    cin >> M;
    while(M--){
        cin >> x;
        cout <<  binarySearch(0, N - 1) << "\n";
    }
}