首页 > 代码库 > 二分法的样例 题解

二分法的样例 题解

题目描述:

 

给定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

样例输出:

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;
}