数字查找题解（博客搬家）

题面

题目描述

输入n个数字，反复查找某个数字是否存在。

输入

第一行n和T，代表n个数字，T次查询 。 接下来一行n个数字 。 接下来T行表示每次查询的数字 。

输出

对于每次查询，查询成功输出"YES"，失败输出"NO"，以换行为间隔。

样例输入

5 3 2 3 1 4 7 6 1 7

样例输出

NO YES YES

提示

数据范围：n<=100000，T<=100000

---

题目分析

这是一道二分算法题，时间复杂度为 $O(log2n)$。

主要思路

将所有给出的数据排列， 建立两个指针 $l$ 和 $r$，初始时分别居于排列好的数组两侧。$l=0$，$r=n$。 找到数据的中点 $m$， 并判断我们要查找的数与中点 $m$ 的关系。 众所周知 当我们要查找的数小于 $m$ 时，说明数据在 $l$ 和 $m$ 的范围内，那么我们就可以把右指针 $r$ 变为 $m+1$。 当我们要查找的数大于 $m$ 时，说明数据在 $m$ 和 $r$ 的范围内，那么我们就可以把左指针 $l$ 变为 $m-1$。 执行完上述操作后，我们需要继续判断下一个中点，直到左指针 $l$ 大于等于右指针 $r$。 如果找到了，就返回这个数已找到。 如果左指针 $l$ 大于等于右指针 $r$ 时还没有找到，说明在给出的数据中没有符合要求的数，我们就可以返回这个数查询失败。 最后判断输出。

code

#include <bits/stdc++.h> using namespace std; int a[100001],mid; int js(int l,int r,int x) { while(l<=r) { mid=l+(r-l)/2; if(x==a[mid]) return 1; else if(x>a[mid]) l=mid+1; else r=mid-1; } return 0; } int main() { int n,t,s,l,r; scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<=t;i++) { l=1; r=n; scanf("%d",&s); if(js(l,r,s)==1) printf("YES\n"); else printf("NO\n"); } return 0; }