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