[BOJ 1920] 수 찾기

수는 10만개 있는데

쿼리도 10만개이니까

한 번의 쿼리를 O(N)으로 탐색해서는 안 된다.

 

정렬 한 번 한 뒤에

이분탐색으로 찾고자 하는 숫자가 있는지 없는지 알아내면 된다.

 

같은 숫자가 여러개 들어올 때

lower bound나 upper bound를 찾을 때에는 아래와 같이 짜면

틀릴 수 있다.

하지만 지금은 해당 숫자가 '존재하느냐'를 물었기에,

같은 숫자가 있는 경우를 전혀 고려할 필요가 없다.

어차피 [l, r] 내에 찾고자 하는 숫자가 존재할 것이기 때문이다.

 

그리고 이분탐색이 이렇게 티어가 낮았나 싶은데

백준 단계별 풀기는 문제 밑에 힌트를 써주기 때문에

이분탐색인걸 알 수 있는 점도 체감 난이도를 낮추는 데 한 몫 한 것 같다.

(물론 공부를 터레끼만큼이라도 했으면 이 문제가 이분탐색 문제인 걸 알아차리는데 1분도 걸리지 않아야 한다)

 

#include <bits/stdc++.h>

using namespace std;

int n, m;
int a[100000];

int f(int t) {
	int l = 0, r = n - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		if (a[m] == t) {
			return 1;
		} else if (a[m] < t) {
			l = m + 1;
		} else if (a[m] > t) {
			r = m - 1;
		}
	}
	return 0;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	cin >> m;
	while (m--) {
		int t; cin >> t;
		cout << f(t) << '\n';
	}
	return 0;
}