21天搞定考研机试（16）

途家网

2.7 查找类问题

查找是一类我们必须掌握的算法，它不仅会在题目中直接考察，同时也可能是其他算法中的重要组成部分。本章中介绍的查找类问题都是单独的基础查找问题，对于这类基础查找的问题，我们应该将它完全掌握。
查找类题目一般有以下几种考点
1、数字查找：给你一堆数字，让你在其中查找x是否存在
题目变形：如果x存在，请输出有几个。
2、字符串查找：给你很多个字符串，让你在其中查找字符串s是否存在
顺序查找就不说了，这个大家会。
什么时候不能用顺序查找呢？
很明显，当满足下面这种情况的时候
1、数据量特别大的时候，比如有10W个元素。
2、查询次数很多的时候，比如要查询10W次。
遇到这类题大多数人的想法是先sort排序，然后二分查找，这是一个很常规的解决这类问题的方法。
但是，我们不推荐你这么做，我们有更简单易用且快速的方法。我们推荐你了解并使用map容器。
前面介绍过map，它是STL的一种关联式容器，它的底层是红黑树实现的，也就意味着它的插入和查找操作都是log级别的。
相信每一个用过map的同学，都会情不自禁的说一句，map真香！
查找学生信息2
题目描述：
输入N个学生的信息，然后进行查询。
输入描述：
输入的第一行为N，即学生的个数(N<=1000)
接下来的N行包括N个学生的信息，信息格式如下：
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下：
02
03
01
04
输出描述：
输出M行，每行包括一个对应于查询的学生的信息。
如果没有对应的学生信息，则输出“No Answer!”
输入样例#:
4
01 李江 男 21
02 刘唐 男 23
03 张军 男 19
04 王娜 女 19
5
02
03
01
04
03
输出样例#:
02 刘唐 男 23
03 张军 男 19
01 李江 男 21
04 王娜 女 19
03 张军 男 19
题目来源：
DreamJudge 1476
题目解析：对于这类查询量大的题目，我们有两种方法来解决这个问题。第一是将学号先排好序，然后使用二分查找，但是很多同学写二分的时候容易出现问题，而且代码量也比较大，我们不推荐这种做法。推荐大家使用map来解决这类问题，基本上map可以通过99.9%的这类题目。
参考代码
1. #include <bits/stdc++.h>
2. using namespace std;  
3.  
4. struct node{  
5.     string num;  
6.     string name;  
7.     string sex;  
8.  int age;  
9. };  
10. int main(){  
11.  int n,q;  
12.     map<string, node> M;//定义一个map映射
13.  while(scanf("%d", &n)!=EOF){  
14.  for(int i=0;i<n;i++){  
15.             node tmp;  
16.             cin>>tmp.num>>tmp.name>>tmp.sex>>tmp.age;  
17.             M[tmp.num] = tmp;//将学号指向对应的结构体
18.         }  
19.         scanf("%d", &q);  
20.  for(int i=0;i<q;i++){  
21.             string num;  
22.             cin>>num;  
23.  if((M.find(num))!=M.end())//find查找 如果找不到则返回末尾
24.                 cout<<M[num].num<<" "<<M[num].name<<" "<<M[num].sex<<" "<<M[num].age<<endl;  
25.  else
26.                 cout<<"No Answer!"<<endl;  
27.         }  
28.     }  
29.  return 0;  
30. }  
可以发现，用map解决这个题目的时候，不用去考虑字符串排序的问题，也不用想二分查找会不会写出问题，直接用map，所有的烦恼都没有了，而且它的复杂度和二分查找是一个量级的。
上面讲的是一类静态查找的问题，实际中为了增加思维难度或代码难度，会经过一定的改变变成动态查找问题。
动态查找问题
题目描述：
有n个整数的集合，想让你从中找出x是否存在。
输入描述：
第一行输入一个正整数n（n < 100000）
第二行输入n个正整数，用空格隔开。
第三行输入一个正整数q（q<100000），表示查询次数。
接下来输入q行，每行一个正整数x，查询x是否存在。
输出描述：
如果x存在，请输出find，如果不存在，请输出no，并将x加入到集合中。
输入样例#:
5
1 2 3 4 5
3
6
6
3
输出样例#:
no
find
find
题目来源：
DreamJudge 1477
题目解析：通过分析题目我们可以发现，这道题有一个特点就是，数的集合在不断的改变。如果我们用先排序再二分的方法就会遇到困难，因为加入新的数的时候我们需要去移动多次数组，才能将数插入进去，最坏情况每次插入都是O(n)的复杂度，这是无法接受的。当然也不是说就不能用这样的方法来解决了，可以用离线的方法来解决这个问题，但是这样做太复杂，不适合在考试中使用。那么我们考虑用map来解决这个问题。
参考代码
1. #include <bits/stdc++.h>
2. using namespace std;  
3.  
4. int main(){  
5.  int n,q,x;  
6.     map<int, int> M;//定义一个map映射
7.     scanf("%d", &n);  
8.  for (int i = 0; i < n; i++) {  
9.         scanf("%d", &x);  
10.         M[x]++;//记录集合中x有多少个
11.     }  
12.     scanf("%d", &q);  
13.  for (int i = 0; i < q; i++) {  
14.         scanf("%d", &x);  
15.  if (M[x] == 0) {//如果x的个数为0
16.             printf("no\n");  
17.             M[x]++;//将x加入到集合中
18.         }  
19.  else printf("find\n");  
20.     }  
21.  return 0;  
22. }
看了上面的代码，是不是发现用map来解决问题真是超级简单。所以学会灵活使用map将能极大的拉近你和大佬之间的距离，我们一起来学map吧！
当然不是说二分查找就没用了，我们也需要了解二分查找的原理，只不过。二分的前提是单调性，只要满足单调性就可以二分，不论是单个元素还是连续区间。下面我们也给出一个基本的二分查找代码，供大家参考。
1. #include <bits/stdc++.h>
2. using namespace std;  
3.  
4. int a[10005];  
5. int main(){  
6.  int n,x;  
7.     scanf("%d", &n);//输入n个数
8.  for (int i = 1; i <= n; i++) {  
9.         scanf("%d", &a);  
10.     }  
11.     sort(a+1, a+1+n);//排序保持单调性
12.     scanf("%d", &x);//要查找的数x
13.  int l = 1, r = n;  
14.  while (l < r) {  
15.  int mid = (l + r) / 2;  
16.  if (a[mid] == x) {  
17.             printf("find\n");  
18.  return 0;  
19.         }  
20.  if (a[mid] > x) {//如果x比中间数小
21.             r = mid - 1;//说明在左区间
22.         }  
23.  else l = mid + 1;//否则在右区间内
24.     }  
25.     printf("not find\n");  
26.  return 0;  
27. }  

练习题目
DreamJudge 1177 查找学生信息
DreamJudge 1388 查找1
DreamJudge 1387 查找 - 北邮
DreamJudge 1383 查找第K小数

刀郎哥

very good