二分查找题目分析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。不再提供样例程序。