查找（二分、hash、桶）

先上一个最简单的题

1230 元素查找

给出n个正整数，然后有m个询问，每个询问一个整数，询问该整数是否在n个正整数中出现过。

输入描述 Input Description

第一行两个整数 n 和m。

第二行n个正整数（1<=n<= 100000）

第三行m个整数(1<=m<=100000)

输出描述 Output Description

一共m行，若出现则输出YES，否则输出NO

这个题数据很小，既可以用二分、桶、做，也可以用hash来做

用桶的思想来做的话是最简单的，定义一个bool数组，出现的正整数在数组里标记为TRUE；查找sum有没有出现过时只需要调用bool下标为sum的数组就行。

#include<iostream>
using namespace std;

bool s[100005];
int m,n;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        int sum;
        cin>>sum;
        s[sum]=true;
    }
    for(int i=1;i<=m;++i)
    {
        int sum;
        cin>>sum;
        if(s[sum])cout<<"YES
";
        else cout<<"NO
";
    }
    return 0;
}

如果数据进一步升级，出现过的数进一步增大，空间进一步限制，这时用bool就不行了，需要用到二分查找，先存数，然后查找即可；

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

bool boo[150000];
int s[150000];
int n,m;

bool  find(int sum)
{
    int right=n,left=1;
    while(right>=left)
    {
        int mid=left+(right-left)/2;
        if(s[mid]==sum)return true;
        if(mid<sum)left=mid+1;
        else right=mid-1;
    }
    return 0;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>s[i];
    sort(s+1,s+n+1);
    for(int i=1;i<=m;++i)
    {
        int sum;
        cin>>sum;
        if(find(sum))
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

最后，如果再进一步升级，咳咳，还是用hash吧；

这里是把数模一个数，然后建立以余数和数的边，查找是将待查找的数取余，查找余数所连接的边。

#include<iostream>
#define mod 4567;
using namespace std;

struct node
{
    int a,b,next;
};
node s[100006];

int head[100005],sum=1;
int m,n;

void push(int a,int b)
{
    s[sum].a=a;
    s[sum].b=b;
    s[sum].next=head[a];
    head[a]=sum++;
}

bool find (long long sum)
{
    int x=sum%mod;
    int y=sum/mod;
    for(int k=head[x];k!=-1;k=s[k].next)
        if(s[k].b==y)return true;
}

int main()
{
    for(int i=1;i<=69439;++i)
        head[i]=-1;
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=m;++i)
    {
        long long sum;
        cin>>sum;
        int x=sum%mod;
        int y=sum/mod;
        push(x,y);
    }
    for(int i=1;i<=n;++i)
    {
        long long sum;
        cin>>sum;
        if(find(sum))
            cout<<"YES
";
        else cout<<"NO
";
    }
    return 0;
}

 当然，选用其他的hash函数也是可以的，例如将数的每一位数字加起来，建立边表；当然，选择hash函数的原则对于每一个映射有尽量少的值与之对应，也就是一一对应关系

例如：hash函数%10;则对于1和11，他们对应的hash值一样，就需要存储下每个值，那么算法就会变慢，n为映射值相同的数的数目。

当然，hash所映射的不光是整数，字符串也可以；

现在我又找到了另外一种方法，用STL里的容器MAP就可以；

map是一种关联容器，恩。

看了下百科，表示没看懂；

#include<iostream>
#include<map>
using namespace std;
map<string,int>mapp;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        string s;
        cin>>s;
        mapp.insert(map<string,int>::value_type(s,i));
    }
    while(m--)
    {
        string number;
        cin>>number;
        if(mapp.count(number))
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    //    if(mapp.find(number)!=mapp.end())
    //        cout<<"YES"<<endl;
    //    else cout<<"NO"<<endl;
    }
    return 0;
}