Q. 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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

출력.

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

 


 

10815번과 동일한 문제이다. 단순히 출력 형식만 바꾸어 주면 된다.

 

#include <stdio.h>
#include <stdlib.h>

int bin_search(const int a[], int n, int key)
{
	int pl = 0;
	int pr = n - 1;

	do {
		int pc = (pl + pr) / 2;

		if (a[pc] > key)
			pr = pc - 1;
		else if (a[pc] < key)
			pl = pc + 1;
		else
			return 1;
	} while(pl <= pr);

	return 0;
}

int int_cmp(const int *a, const int *b)
{
	if(*a < *b)
		return -1;
	else if(*a > *b)
		return 1;
	else
		return 0;
}

int main(void)
{
	int i;
	int n, m;
	int *a, *b;

	scanf("%d", &n);

	a = (int*)calloc(n, sizeof(int));

	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	scanf("%d", &m);

	b = (int*)calloc(m, sizeof(int));

	for (i = 0; i < m; i++)
		scanf("%d", &b[i]);

	qsort(a, n, sizeof(int), (int(*)(const void *, const void *))int_cmp);

	for (i = 0; i < m; i++)
		printf("%d\n", bin_search(a, n, b[i]));

	return 0;
}

 

'백준 알고리즘' 카테고리의 다른 글

[C언어] 2292번  (0) 2020.04.11
[C언어] 2872번  (0) 2020.04.11
[C언어] 2869번  (0) 2020.04.05
[C언어] 10815번  (0) 2020.04.04
[C언어] 1568번  (0) 2020.03.04

+ Recent posts