10815번: 숫자 카드

카드의 개수가 많기 때문에 순차적으로 탐색한다면 시간초과가 난다.

이분 탐색을 이용해 시간복잡도를 줄이면 정답을 얻을 수 있다.

#include <iostream>
#include <algorithm>
 
int user1Card[500001] = { 0 };
int user1Count, user2Count;
 
int search(int val, int front, int end) {
    int mid = (front + end) / 2;
//    std::cout << val << ", " << user1Card[mid] << "\n";
    if (val < user1Card[mid]) {
        if(front >= mid) { return 0; }
        return search(val, front,mid - 1);
    }
    else if (val > user1Card[mid]) {
        if(end <= mid) { return 0; }
        return search(val, mid + 1, end);
    }
    else if (val == user1Card[mid]) {
        return 1;
    }
 
}
 
int main(void) {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
 
    std::cin >> user1Count;
    for(int i = 0; i < user1Count; i++) {
        std::cin >> user1Card[i];
    }
 
    std::sort(user1Card, user1Card + user1Count);
 
    std::cin >> user2Count;
    int val;
    for(int i = 0; i < user2Count; i++) {
        std::cin >> val;
        int check = 0;
        if(val >= user1Card[0] && val <= user1Card[user1Count - 1]) {
            check = search(val, 0, user1Count - 1);
        }
 
        std::cout << check << " ";
    }
 
 
    return 0;
}