[class2] (백준 1920) 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2³¹ 보다 크거나 같고 2³¹보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

제한

예제 입력 1

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1

1
1
0
0
1

힌트

출처

• 문제의 오타를 찾은 사람: bupjae
• 잘못된 데이터를 찾은 사람: tncks0121

 

#include <iostream>
using namespace std;
int temp[100000];
void MergeSort(int list[],int start,int mid, int end)
{
	int i = start;
	int j = mid + 1;
	int c = start;
	while (i <= mid && j <= end)
	{
		if (list[i] > list[j])
			temp[c++] = list[j++];
		else
			temp[c++] = list[i++];
	}

	while (i <= mid)
		temp[c++] = list[i++];

	while (j <= end)
		temp[c++] = list[j++];

	for (int q = start; q <= end; q++)
		list[q] = temp[q];

}
void Merge(int list[], int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		Merge(list, start, mid);
		Merge(list, mid + 1, end);
		MergeSort(list, start, mid, end);
	}
}

int BinarySerch(int findValue,int list[],int start,int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		if (list[mid] == findValue)
			return 1;
		else if (list[mid] > findValue)
			return BinarySerch(findValue, list, start, mid);
		else
			return BinarySerch(findValue, list, mid + 1, end);
	}
	else
		return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int k, q;
	int arr[2][100000];
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> arr[0][i];
	}
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> arr[1][i];
	}
	Merge(arr[0],0,k-1);
	for (int i = 0; i < q; i++)
	{
		cout <<BinarySerch(arr[1][i], arr[0], 0, k)<<"\n";
	}
	return 0;
}