首页 > 代码库 > 二分法的样例 题解
二分法的样例 题解
题目描述:
给定N个整数,M个问题
对于每个问题,你需要回答数字A是否在N个数字里出现过
输入:
第一行是两个整数N和M ( 0 < N , M < 100000)
接下来的一行,共有N个整数
接下来的M行,每行有1个整数A
输出:
共M行,
对于每个询问,若A出现过,则输出YES
否则 输出NO
样例输入:
5 2
1 2 3 4 5
5
0
样例输出:
YES
NO
C语言代码:
#include <stdio.h>
#include <stdlib.h>
#define N 1000001
int num[N];
int n, m;
void Read();
int Mycmp(const void *a, const void *b);
int BinSearch(int x);
int main()
{
int x;
scanf("%d %d", &n, &m);
Read();
qsort(num, n, sizeof(int), Mycmp);
while (m--)
{
scanf("%d", &x);
if (BinSearch(x) == -1)
{
puts("NO");
}
else
{
puts("YES");
}
}
return 0;
}
void Read()
{
int i;
for (i=0; i<n; ++i)
{
scanf("%d", &num[i]);
}
return;
}
int Mycmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int BinSearch(int x)
{
int high, low, mid;
high = n - 1;
low = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (num[mid] > x)
{
high = mid - 1;
}
else if (num[mid] < x)
{
low = mid + 1;
}
else
{
return 1;
}
}
return -1;
}