题目描述
输入两个数组,判断第二个数组中的每一个元素是否在第一个数组中出现过。
出现过就输出YES
,否则输出NO
思路:
1.先将第一个数组排序
2.使用二分查找
输入样例:
5
1 5 2 4 3
3
2 5 6
输出样例:
YES
YES
NO
C代码
#include <stdio.h>
#include <stdlib.h>
//一趟快排
int QKSort(int* arr, int low, int high) {
int l = low;//左下标,从最左边开始
int h = high;//右下标,从最右边开始
int pivot = arr[l];//以第一个数为基准值
while (l < h)
{
//首先在pivot的右边一直找,找到小于或者等于pivot的值才退出
while (arr[h] >= pivot && l < h) {
h--;
}
if (l < h)//找到了小于pivot的元素,送入“空单元”(这里的空单元不是真的空,只是被覆盖了)
{
arr[l] = arr[h];
l++;
}
//之后再在pivot的左边一直找,找到大于或者等于pivot的值才退出
while (arr[l] <= pivot && l < h) {
l++;
}
if (l < h)//找到了大于pivot的元素,送入“空单元”(这里的空单元不是真的空,只是被覆盖了)
{
arr[h] = arr[l];
h--;
}
}
arr[l] = pivot;//当退出while循环时,就将基准值归位,即放到当前l的位置;将基准值放到low==high的位置
return l;//返回基准值的下标
}
//快速排序
void Quick_Sort(int* arr, int low, int high) {
int pivotpos = 0;//用来保存枢轴元素的下标
if (low < high)
{
pivotpos = QKSort(arr, low, high);//调用一次快速排序,以枢轴原元素为界划分两个子表,得到枢轴元素的下标
Quick_Sort(arr, low, pivotpos - 1);//递归,对左子表快速排序
Quick_Sort(arr, pivotpos + 1, high);//递归,对右子表快速排序
}
}
int main() {
int n, m;
scanf("%d", &n);
int* ai = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
scanf("%d", &ai[i]);
}
Quick_Sort(ai,0,n-1);//快排
scanf("%d", &m);
int* bi = (int*)malloc(sizeof(int) * m);
for (int i = 0; i < m; i++)
{
scanf("%d", &bi[i]);
}
for (int i = 0; i < m; i++)
{
//二分查找
int low = 0;
int high = n - 1;
int mid;
bool flag = false;
while (low <= high) {
mid = (low + high) / 2;
if (ai[mid] == bi[i])
{
flag = true;
break;
}
else if (ai[mid] < bi[i])
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
if (flag)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}