#10815. 숫자카드

https://www.acmicpc.net/problem/10815

1. 문제 이해

전형적인 탐색 문제입니다. 

2. 접근 방법

완전 탐색을 하되, 이분탐색으로 시간을 줄이도록 하겠습니다. 

저는 재귀로 이분탐색 함수를 작성할 것입니다.

재귀로 함수를 작성할때는 무한 루프에 빠지지 않게 탈출 조건을 먼저 만들도록 합니다!!

3. 문제 해결

#include <algorithm>
#include <cstdio>
#define MAX_SIZE 500001
using namespace std;
 
int n, m;
int my[MAX_SIZE];
int chk[MAX_SIZE];
 
bool bs(int l, int r, int find) {
    int mid = (l + r) / 2;
 
    if (l > r) {
        return false;
    }
    else {
        if (my[mid] == find) return true;
        else if (my[mid] > find) return bs(l, mid - 1, find);
        else return bs(mid + 1, r, find);
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &my[i]);
    }
    sort(my, my + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &chk[i]);
    }
 
    for (int i = 0; i < m; i++) {
        int left = 0, right = n - 1;
        
        if (bs(0, n - 1, chk[i])) {
            printf("1 ");
        }
        else {
            printf("0 ");
        }
    }
    printf("\n");
    return 0;
}

※ 항상 void로 함수를 작성하던 버릇에서 벗어나 좀더 세련되게 짜보았다.

※ cin, cout 보다는 scanf, printf가 빠르다!!