[백준 10815] 숫자 카드

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

10815번: 숫자 카드

 

요구사항

1. 목록에서 주어진 수 찾기

 

풀이

1. 목록 정렬

2. 이분 탐색으로 찾기

다른 풀이

1. 해시

 

이분 탐색 풀이

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, m;
ll map[500001];
ll buf[500001];
ll tans = 0;
ll maxv = 0;
ll minv = 0;
bool check(ll k) {
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (map[i] - k > 0) {
			ans += (map[i] - k);
		}
		if (ans >= m)
			return true;
	}
	if (ans >= m)
	{
		return true;
	}
	else {
		return false;
	}
}
bool com(ll a, ll b)
{
	return (a < b);
}
int Find(ll k) {
	ll left = 0;
	ll right = n;
	ll mid = 0;
	//cout << "M" << maxv << " minv" << minv << endl;
	while (left <= right) {
		mid = (left + right) / 2;
		if (map[mid]==k)
			return 1;
		if (k > map[mid]) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return 0;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%lld", &map[i]);
	}
	sort(map, map +( n));
	cin >> m;
	for (int i = 0; i < m; i++) {
		scanf("%lld", &buf[i]);
		printf("%d ", Find(buf[i]));
	}




}