牛客网 查找（二分查找）

题目描述

输入数组长度 n 输入数组 a[1…n] 输入查找个数m 输入查找数字b[1…m] 输出 YES or NO 查找有则YES 否则NO 。
输入描述:
输入有多组数据。
每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m,n<=100）。

输出描述

如果在n个数组中输出YES否则输出NO。
示例1

输入

5
1 5 2 4 3
3
2 5 6

输出

YES
YES
NO

Solution

二分查找板题。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1111;
int num[maxn];
int low_bound(int first, int last, int value)
{
    while (first < last)
    {
        int mid = first + (last - first) / 2; // 防溢出
        if (value > num[mid])
            first = mid + 1;
        else
            last = mid;
    }
    return first;
}
int main()
{
    // freopen("in.txt", "r", stdin);
    int n, m;
    while (~scanf("%d", &n))
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);
        sort(num, num + n);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
        {
            int value;
            scanf("%d", &value);
            int index = low_bound(0, n, value);
            if (value == num[index])
                puts("YES");
            else
                puts("NO");
        }
    }
    return 0;
}