首页 > 试题广场 >

查找

[编程题]查找
  • 热度指数：34112 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入数组长度 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
算法知识视频讲解
添加回答
小陈也只是想要一个实习罢了头像 小陈也只是想要一个实习罢了 
//先记一个别的做法，这个空间换时间做的还是不错的，o(m)的时间，就是这个范围有点难确定
#include<bits/stdc++.h>
int main(){
    int m,n,s;
    while(scanf("%d",&n)!=EOF){
        int a[1000]={0};
        for(int i=0;i<n;i++){
            scanf("%d",&m);
            a[m]=1;
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&s);
            if(a[s]==1) printf("YES\n");
            else printf("NO\n");
        }
    }
}//hash法
//下面这个自己写的时间复杂度是o(m*n)因为感觉说了m,n的范围都在100以内，所以即使乘积也不会超限
#include<iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n){
        int *a=new int[n],b;
        for(int i=0;i<n;i++)
            cin>>a[i];
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>b;
            bool judge=1;
            for(int j=0;j<n&&judge;j++)
                if(b==a[j]){
                    cout<<"YES"<<endl;
                    judge=0;
                }
            if(judge)
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

发表于 2020-01-14 15:29:12 回复(2)
C/C++
Medivh!头像 Medivh! 
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int x[102];
    int n, q, m;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        sort(x, x+n);
        cin >> m;
        while (m--) {
            cin >> q;
            cout << ((*lower_bound(x, x+n, q) == q) ? "YES" : "NO") << endl;
        }
    }
}

发表于 2018-03-15 11:24:09 回复(0)
C/C++
My_C头像 My_C 
#include <iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n){
        int i,a[100],b[100];
        for(i=0;i<n;i++)
            cin>>a[i];
        cin>>m;
        for(i=0;i<m;i++)
            cin>>b[i];
        for(i=0;i<m;i++){
            bool flag=false;
            for(int j=0;j<n;j++){
                if(b[i]==a[j]){
                    flag=true;
                    break;
                }
            }
            if(flag) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}
发表于 2017-12-13 17:57:44 回复(0)
啥也不是1024头像 啥也不是1024 
#include <bits/stdc++.h>
using namespace std;
int x,n,m,num[100];	
map<int,int> M;
int main()
{
    cin>>n;   
	for(int i =0;i<n;i++)
	{
        cin>>x;
		M[x]++;
	}
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>num[i];
    for(int i =0;i<m;i++)
    {
        if(M[num[i]]==0)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
	return 0;
}
利用Map查找





发表于 2020-03-04 12:47:50 回复(0)
发愤图强的小菜头像 发愤图强的小菜
时间复杂度O(n) 
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        while (in.hasNext()){
            int n=in.nextInt();
            Set<Integer> set=new HashSet<Integer>();

            for (int i=0;i<n;i++)
                set.add(in.nextInt());

            n=in.nextInt();
            for (int i=0;i<n;i++){
                int a=in.nextInt();
                if (set.add(a))
                {
                    set.remove(a);
                    System.out.println("NO");
                }

                else
                    System.out.println("YES");
            }

        }
    }
}


发表于 2017-05-26 14:59:19 回复(0)
C/C++
KDDA十三尧十三头像 KDDA十三尧十三 
#include<iostream>
#include<vector>
using namespace std;

int main(void)
{
    int n;
    vector<int> a;
    vector<int> b;
    
    while(cin >> n)
    {
        for(int i = 0;i < n;i++)
        {
            int x;
            cin >> x;
            a.push_back(x);
        }
        
        int m;
        cin >> m;
        for(int i = 0;i < m;i++)
        {
            int y;
            cin >> y;
            b.push_back(y);
        }
        
        for(int i = 0;i < m;i++)
        {
            int count = 0;//标记是否有相同数字的个数
            for(int j = 0;j < n;j++)
            {
                if(b[i] == a[j])
                    count++;
            }
            if(count == 0)
                cout << "NO" << endl;
            else
                cout << "YES" << endl;
        }
    }
    return 0;
}

发表于 2021-02-22 16:19:52 回复(0)
C/C++
想了三天不知道叫什么头像 想了三天不知道叫什么 
#include<stdio.h>
#include<stdlib.h>

//比较函数
int cmp_inc(const void* a,const void* b){
    return *(int *)a - *(int *)b;
}

//二分查找
int Binary_Search(int *arr,int n,int key){
    int low=0;
    int high=n-1;
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]<key){
            low=mid+1;
        }
        else{
            high=mid-1;
        }
    }
    return -1;
}

int main(){
    int n,m;
    int a[100];
    int b[100];
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        qsort(a,n,sizeof(int),cmp_inc);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d",&b[i]);
        }
        for(int i=0;i<m;i++){
            int s=Binary_Search(a,n,b[i]);
            if(s!=-1){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
}


编辑于 2021-01-31 11:44:47 回复(0)
mrvoider头像 mrvoider 
#include <bits/stdc++.h>

using namespace std;

int a[101],b[101];
bool flag[101];

int main()
{
    int n,m;
    int i;
    scanf("%d",&n);
    for(i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a, a+n);
    scanf("%d",&m);
    for(i = 0; i < m; i++)
    {
        scanf("%d",&b[i]);
        flag[i] = binary_search(a, a+n, b[i]);
    }
    for(i = 0; i < m;i++)
    {
        if(flag[i]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    return 0;
}
好像用STL好像没什么意思，反正思路是这样的。。
发表于 2021-01-27 21:24:48 回复(0)
道纪书生头像 道纪书生 
#include<bits/stdc++.h> //万能头
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;

int BinarySearch(int a[],int n,int b)
{
	int left=0;
	int right=n-1;
	while(left<=right)
	{
		int middle=(left+right)/2;
		if(a[middle]<b)
		{
			left=middle+1;
		}
		else if(b<a[middle])
		{
			right=middle-1;
		}
		else
		{
			return 1;
		}
	}
	return 0;
	
}

int main(){
	int m,n;
	while(scanf("%d",&n)!=EOF)
	{
		int a[n];
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		scanf("%d",&m);
		sort(a,a+n);
		int b[m];
		for(int i=0;i<m;i++)
		{
			scanf("%d",&b[i]);
		}
		for(int i=0;i<m;i++)
		{
			if(BinarySearch(a,n,b[i] )==1)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
		
		
	} 
    return 0;
}

发表于 2020-09-10 10:45:24 回复(0)
Java
LHC0512头像 LHC0512
Java解法 
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) set.add(scanner.nextInt());
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) System.out.println(set.contains(scanner.nextInt())?"YES":"NO");
    }
}


发表于 2020-03-14 16:29:34 回复(0)
C/C++
Orin头像 Orin
#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n,m;
    int buf[100];
    int top,base,mid;
    int ans=-1;
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++)
            scanf("%d",&buf[i]);
        sort(buf,buf+n);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            ans=-1;
            int tmp;
            scanf("%d",&tmp);
            top=n-1;
            base=0;
            mid=(top+base)/2;
            while(base<=top){
                if(buf[mid]==tmp){
                    ans=1;
                    break;
                }
                else{
                    (buf[mid]>tmp)?(top=mid-1):(base=mid+1);
                    mid=(top+base)/2;
                }
            }
            if(ans==-1)    printf("NO\n");
            else    printf("YES\n");
        }
    }
    return 0;
}
发表于 2019-04-30 11:48:51 回复(0)
hushhw头像 hushhw 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
using namespace std;

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int num;
        set<int> a;
        for (int i = 0; i<n; i++){
            scanf("%d", &num);
            a.insert(num);
        }
        int m,c;
        scanf("%d", &m);
        for (int i = 0; i < m; i++){
            scanf("%d", &c);
            if(a.find(c)!=a.end()){
                printf("YES\n");
            }else{
                printf("NO\n");
            }
        }
    }
    return 0;
}
发表于 2019-03-01 19:36:06 回复(0)
sunlanchang头像 sunlanchang

二分查找STL中bug-free实现

#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;
}
编辑于 2019-01-31 19:05:47 回复(0)
明达超级幸运(ง•_•)ง头像 明达超级幸运(ง•_•)ง 
#include<stdio.h>
#include<algorithm>
using namespace std;
int solve(int a[],int left,int right,int k){
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(k<=a[mid])
            right=mid;
        else
            left=mid+1;
    }
    return left;
}
int main(){
    int n,a[100];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int m,b[100];
    scanf("%d",&m);
    for(int i=0;i<m;i++)
        scanf("%d",&b[i]);
    sort(a,a+n);
    int j=0,r;
    while(j<m){
        r=solve(a,0,n-1,b[j]) ;
        if(b[j]==a[r]){
            printf("YES\n");
        }
        else
            printf("NO\n");
        j++;
   }
    return 0;
}

发表于 2019-01-22 15:37:27 回复(0)
Benson666头像 Benson666 
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int n,m;
    while(scanf("%d", &n)!=EOF){
        int a[10000];
        for(int i=0;i<n;i++){
            int tmp;
            cin>>tmp;
            a[tmp] = 1;
        }
        cin>>m;
        for(int i=0;i<m;i++){
            int tmp;
            cin>>tmp;
            if(a[tmp]==1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}

发表于 2018-03-19 16:17:55 回复(1)
C/C++
东子201803081322909头像 东子201803081322909
//有两点需要注意，一是yes和no的输出由token控制；二是如果例子中由两个测试数据需要用break跳出以免输出两个yes
#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{   int m,n,token=0;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&m);
    int b[m];
    for(int i=0;i<m;i++)
        scanf("%d",&b[i]);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(b[i]==a[j]){
            printf("YES\n");
            token=1;
            break;
           }
        }
        if(token==0)
        printf("NO\n");
        token=0;
    }
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

发表于 2018-03-17 21:42:09 回复(0)
C/C++
叮哩当啷头像 叮哩当啷
哈希数组法：
//#include<stdio.h>
/*哈希数组每次需要初始化为0*/
#include<iostream>
#include<string.h>
using namespace std;
#define N 100000
int hashs[N];
int main()
{
int n,m,x;
while(cin>>n)
{
memset(hashs,0,sizeof(hashs));
for(int i=0;i<n;i++)
{
cin>>x;
hashs[x]=1;
}
cin>>m;
for(int i=0;i<m;i++)
{
cin>>x;
if(hashs[x]==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
}
return 0;
}

编辑于 2018-01-14 18:06:16 回复(2)
rs勿忘初心头像 rs勿忘初心
     最简单的就是暴力循环比较搜索，需要注意的是谁跟谁比较。如下图，n和m的位置。 

#include <iostream>
using namespace std;
int main( )
       {
         int m,n;
         while(cin>>n)
          {
           int a[n];
           for(int i=0;i<n;i++)
              cin>>a[i];
           cin>>m;
           int b[m];
           for(int j=0;j<m;j++)
               cin>>b[j];
           for(int i=0;i<m;i++)
            {
              for(int j=0;j<n;j++)
               {
                  if(b[i]==a[j])
                     {
                      cout<<"YES"<<endl;
                      break;
                     }
                  if(j==n-1)
                      cout<<"NO"<<endl; 
               }
            }
           }
           return 0;
         }

发表于 2017-04-19 19:32:55 回复(0)
karaysn头像 karaysn

//我理解错了，原来是要拿第二个数组中的每个数和第一个数组中的数字比较

import java.util.Scanner;

public class Main { public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);
    while(sc.hasNext()){
        //第一个数字，也是第一个数组的长度
        int a1=sc.nextInt();
        //定义第一个数组
        int[] a=new int[a1];
        for(int i=0;i<a.length;i++){
            a[i]=sc.nextInt();
        }

        //输入第二个数组的长度
        int b1=sc.nextInt();
        int[] b=new int[b1];
        for(int i=0;i<b.length;i++){
            b[i]=sc.nextInt();
        }

        for(int i=0;i<b.length;i++){
            test(b[i],a);
        }
    }
}

    public static void test(int a1,int[] a){
            boolean flag=false;
            while(!flag){
                for(int i=0;i<a.length;i++){
                    if(a[i]==a1){
                        System.out.println("YES");
                        flag=true;break;
                    }
                }
                break;
            }
            if(flag==false)
                System.out.println("NO");

    }

}

发表于 2017-04-17 10:32:32 回复(0)
依然·范特西头像 依然·范特西 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	int N;
	while (cin >> N)
	{
		int num;
		vector<int> vec;
		for (int i = 0;i < N;++i)
		{
			cin >> num;
			vec.push_back(num);
		}
		int n;
		cin >> n;
		for (int i = 0;i < n;++i)
		{
			cin >> num;
			if (find(vec.begin(), vec.end(), num) != vec.end())
				cout << "YES\n";
			else
				cout << "NO\n";
		}
	}

	return 0;
}

发表于 2017-02-27 19:50:46 回复(0)
提交观点

问题信息

数组 二分 查找
难度：
164条回答 13115浏览

热门推荐

通过挑战的用户

查看代码

相关试题

查找

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号