백준 1920

이진 탐색을 이용한 문제 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void Compare(vector<int> &in, vector<int> &qu, vector<int>& out, int num, int first, int last)
{	

	while (first <=last)
	{
		int mid = (first + last) / 2;
		if (qu[num] == in[mid])
		{
			out.push_back(1);
			return;
		}
		else if (qu[num] < in[mid])
		{
			last = mid - 1;
		}
		else
		{
			first = mid + 1;
		}
	}
	out.push_back(0);
	return;
	
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> inputs;

	int input = 0;

	cin >> input;

	for (int i = 0; i < input; ++i)
	{
		int num = 0;
		cin >> num;
		inputs.push_back(num);
	}
	
	sort(inputs.begin(), inputs.end());

	cin >> input;

	vector<int> qu;

	for (int i = 0; i < input; ++i)
	{
		int num = 0;
		cin >> num;
		qu.push_back(num);
	}


	vector<int> output;

	for (int i = 0; i < qu.size(); ++i)
	{
		Compare(inputs, qu, output, i, 0, inputs.size()-1);
	}
	
	for (int i = 0; i < output.size(); ++i)
	{
		cout << output[i] << "\n";
	}

	return 0;
}