vlambda博客
学习文章列表

二分查找题目分析1-找朋友


题目描述

小学毕业后,同学们都进入了不同的初中,小明非常想念小伙伴们,所以他打算联系小学的同学们。现在他得到了市内某所初中的所有名单,找出其中小明的小伙伴们。

输入

第一行一个整数 n,表示某初中人数。

接下来 n 行,每行一个字符串,只有小写字母组成,表示该校每个人的拼音。数据保证没有名字拼音相同,且已经按照字典序从小到大排序。

第 n+2 行有一个整数 m,表示小明的小伙伴个数。

最后 m 行,每行一个字符串,只有小写字母组成,表示每个小伙伴的拼音,同样保证没有重复。

输出

输出所有在该校的小伙伴的拼音。

每行一个拼音,顺序按照小伙伴给出的顺序。

样例输入

3

alice

bob

zhangsan

2

lisi

zhangsan

样例输出

zhangsan

提示

【样例 1 解释】

学校有 3 人,小伙伴有 2 个,zhangsan 在这个学校,因此输出zhangsan

【输入样例 2】

2

lisi

zhangsan

3

zhangsan

lisi

alice

【输出样例 2】

Zhangsan

lisi

【样例 2 解释】

学校有 2 人,小伙伴有 3 个,有 zhangsan 和lisi 两人出现在名单中,小伙伴名单输入时 lisi 在zhangsan 后面,所以在输出的小伙伴名单中,lisi 排在后面。

【数据范围】

对于 70%的数据,n<=1000,m<=100

对于 100%的数据,n<=100000,m<=10000,每个人拼音长度不超过 15。

所有数据,学校学生名单中的姓名,都是按照字典序从小到大排序。

分析:

1、暴力枚举

用双重循环,小伙伴名单里的每一个名字到学校名单里去搜索,查到就输出小伙伴的名字,并且退出内层循环,再搜索下一个。这样的暴力搜索,在数据范围小的时候,可以满分;搜索大量数据的时候,就会耗时严重。

样例程序1(C语言):

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=1e5;

char c[N+10][20],s[20];

int n,m;

int main(){

   scanf("%d",&n);

    for(inti=0;i<n;i++){

      scanf("%s",c[i]);

    }

    scanf("%d",&m);

    for(inti=0;i<m;i++){

         scanf("%s",s);

         for(intj=0;j<n;j++){

               if(strcmp(c[j],s)==0){

                     printf("%s\n",s);

                     break;

               }

         }

    }

    return 0;

}

注意:字符串输入的用法。字符串函数需要添加头文件<cstring>。字符串比较函数strcmp(字符串a,字符串b),返回值等于0,说明字符串a等于字符串b;返回值大于0,说明字符串a按照字典序大于字符串b;返回值小于0,说明字符串a按照字典序小于字符串b。

样例程序2(C++):

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1e5;

string c[N+10],s;

int n,m;

int main(){

   cin>>n;

    for(inti=0;i<n;i++){

       cin>>c[i];

    }

   cin>>m;

    for(inti=0;i<m;i++){

       cin>>s;

        for(intj=0;j<n;j++){

            if(s==c[j]){

               cout<<s<<endl;

               break;

            }

        }

    }

    return 0;

}

注意:string可以按照字典序直接进行字符串比较。在有大量的读写数据时候,cin、cout比scanf、printf会耗费更多的时间。

2、二分查找

多了不说,直接上程序。

样例程序1(C语言):左闭右开区间的做法[left,right)

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char a[100010][30],b[10020][30];

int main(){

    intn,m,left,right,mid;

    scanf("%d",&n);

    for(inti=0;i<n;i++){

         scanf("%s",a[i]);

    }

    scanf("%d",&m);

    for(inti=0;i<m;i++){

         scanf("%s",b[i]);

    }

    for(inti=0;i<m;i++){

         left=0;right=n;

         while(left<right){

               mid=left+(right-left)/2;

               if(strcmp(b[i],a[mid])>0)left=mid+1;

               elseif(strcmp(b[i],a[mid])<0) right=mid;

               else{

                     printf("%s\n",b[i]);

                     break;

               }

         }

    }

    return 0;

}

样例程序2(C语言):闭区间的做法[left,right]

循环条件left<right改成left<=right;right=mid改成right=mid-1。不再提供样例程序。

样例程序3(C++):

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=1e5;

string c[N+10],s;

int n,m,left,right,mid;

int main(){

   cin>>n;

    for(inti=0;i<n;i++){

      cin>>c[i];

    }

    cin>>m;

    for(inti=0;i<m;i++){

         cin>>s;

         left=0;right=n;

         while(left<right){

               mid=(left+right)/2;

               if(s<c[mid]){

                     right=mid;

               }elseif(s>c[mid]){

                     left=mid+1;

               }else{

                     cout<<s<<endl;

                     break;

               }

         }

    }

    return 0;

}

样例程序4(C++):闭区间做法[left,right]

循环条件left<right改成left<=right;right=mid改成right=mid-1。不再提供样例程序。