【二分1】查询是否存在某个数

前言

• 二分知识讲解

1.二分知识讲解

二分算法是一种高效的查找算法，适用于已经排好序的数组或集合。其基本思想是通过每次将待查找的区间分成两半来逐步缩小查找范围，从而快速定位目标元素。与线性查找不同，二分查找能够大大减少查找次数，时间复杂度为O(log n)，其中n为数组的长度。

题目描述

给定一个升序排列的整数数组 $A$ 和一个整数 $Q$，表示接下来有 $Q$ 次查询。对于每次查询，您需要判断给定的整数 $x$ 是否存在于数组 $A$ 中。请使用二分查找算法实现这一功能。

输入格式

• 第一行包含两个整数 $n$ 和 $Q$（$1 \leq n \leq 10^5$, $1 \leq Q \leq 10^5$），分别表示数组的长度和查询的次数。
• 第二行包含 $n$ 个升序排列的整数 $A_1, A_2, \ldots, A_n$（$1 \leq A_i \leq 10^9$）。
• 接下来的 $Q$ 行，每行包含一个整数 $x$（$1 \leq x \leq 10^9$），表示需要查询的数。

输出格式

对于每个查询，输出一行：

• 如果 $x$ 存在于数组 $A$ 中，输出 "YES"。
• 如果 $x$ 不存在于数组 $A$ 中，输出 "NO"。

示例

输入：

5 3
1 3 5 7 9
3
2
9

输出：

YES
NO
YES