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 |