BOJ 10815번 숫자 카드

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

github : https://github.com/junho0956/Algorithm/blob/master/10815/10815/%EC%86%8C%EC%8A%A4.cpp

 

숫자의 범위가 크기때문에 배열을 이용할 수는 없다.

그래서 탐색을 통해 존재여부를 찾아야하므로 가장 기본적인 binary search 를 아는지 모르는지를 묻는 문제이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v;
 
int search(int s, int e, int k) {
    int mid;
    while (s <= e) {
        mid = (s + e) / 2;
        if (v[mid] == k) return 1;
        else if (v[mid] > k) e = mid - 1;
        else if (v[mid] < k) s = mid + 1;
    }
    if (v[s] == k || v[e] == k) return 1;
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N, n, M, m;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> n;
        v.push_back(n);
    }
    sort(v.begin(), v.end());
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> m;
        cout << search(0, N - 1, m) << ' ';
    }
 
    return 0;
}