백준] 1920 - 수 찾기

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

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

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
bool search(int su, int* arr, int start, int end)
{
	int mid;
	while (1)
	{
		mid = (start + end) / 2;
		if (arr[start] == su || arr[end] == su || arr[mid] == su)
			return true;
		else if (arr[start] < su && su < arr[mid])
			end = mid - 1;
		else if (arr[mid] < su && su < arr[end])
			start = mid + 1;
		else
			return false;
	}
}
int main(void)
{
	int n, m;
	int* arr1;
	int* arr2;

	cin >> n;
	arr1 = new int[n];
	for (int i = 0; i < n; i++)
		cin >> arr1[i];
	sort(arr1, arr1 + n);

	cin >> m;
	arr2 = new int[m];
	for (int i = 0; i < m; i++)
	{
		cin >> arr2[i];
	}

	for (int i = 0; i < m; i++)
	{
		if (search(arr2[i], arr1, 0, n - 1))
			cout << 1 << "\n";
		else
			cout << 0 << "\n";
	}
}

Tip

기본적으로 이 문제는 이진탐색(혹은 이분탐색)의 기초 내용을 배웠다면 곧장 풀 수 있을 정도로 매우 기본적인 문제로, 당장 구현해내고 간단한 입출력만 구현하면 정확한 답을 받아낼 수 있다.