浅谈查找与搜索
浅谈是不可能浅谈的，这辈子都不可能浅谈的
（注：涉及程序统一为c++）
查找
嗯，怎么说呢…… 查找是在大量的信息中寻找一个特定的信息元素，查找是常用的基本运算，例如数组查找，字符串查找等等。
算法总结：
1、顺序查找法
顺序查找较适合于顺序存储的线性表。（如果够不拘小节可以视为数组）
基本的思想其实很简单啦，从数据结构线性表的一端开始查找，依次将扫描到的结点关键字与给定值相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于给定值的结点，表示查找失败。是不是想到了扫字符串，扫数组的情景？
上代码！！！
int s(int a[], int v, int n)//看，数组！
{
int i;
for(i=0; i<n; i++)//v为给的定值，n嘛，sizeof（a）
if(a[i]==v)
return i;
return （某bool）;//找不到
}（其实也不难嘛）
2、二分查找法
难度上升！
提醒：元素必须是有序的，如果是无序的则要先进行排序操作！（排序来不及讲了）
根据名字就可以得出它的基本思想，用给定值先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据给定值与该中间结点关键字的比较确定下一步查找哪个子表（如果给定值比中间结点关键字大，则在比中间节点关键字大的子表中再次二分，反之就在比中间结点关键字小的子表中再次二分），直到查找到或查找结束发现表中没有这样的结点。
比如说，1到100的正整数，想找89，中间节点关键字应依次为50->75->87->93->90->88->89。（有点恶心是不是）
上代码！！！
int s(int a[], int v, int n)
{
int low, high, mid;
low = 0;
high = n-1;//low与high赋值
while(low<=high)
{
mid = (low+high)/2;//mid中间数的赋值
if(a[mid]==v)
return mid;//查找成功！
if(a[mid]>v)
high = mid-1;//中间节点关键字比v大，到较小子表二分
if(a[mid]<v)
low = mid+1;//中间节点关键字比v小，到较大子表二分
}
return （某bool）;//找不到
}3、二叉树查找
（记得打星哦）
二叉树查找属于比较简单的树表查找，限于篇幅我们先介绍这种算法。
介绍几个概念：
图片地址：https://img.it610.com/image/info5/4ba27448bf324743908bed5715fb919a.jpg
如图，
（1）我们把图中A节点称为这棵二叉树的根节点；
（2）图中B节点是A节点的左儿子，C节点是A节点的右儿子，A节点是B、C节点的父亲节点；
（3）如果把二叉树用数字从上到下，从左到右编号，那么每个父亲节点k若有左儿子，左儿子编号必为2k，若有右儿子，右儿子编号必为2k+1；
（4）在二叉树的第i层（i是正整数），最多有2^（i-1）个结点；
（5）深度为k的二叉树（k是非负整数）最少有k个结点，最多有2^k-1个结点（与2^（k-1）不同呦~）。
基本概念到此结束，其他可以自行学习！
二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
什么？你问我中序遍历是什么？不要急，听我慢慢道来：
再次引用此图，二叉树的遍历分为三种，是前序遍历，中序遍历和后序遍历。
你可以这样想：前序遍历：根左右；中序遍历：左根右；后序遍历：左右根。
怎么解释？
比如说图中二叉树的前序遍历为：ABDECFG(有点像我们马上要讲的深搜），先从根节点开始不断往左深入一直到最后一个子节点D，之后一步一步返回（就像递归一样），如果发现了某个右儿子就加入序列，如果这个右儿子下面还有儿子，我们暂时把它当作“父亲节点”，继续往下扫，这样循环下来，直到返回最初的父结点为止。
根据这个思路我们也可以得出上图的中序遍历：DBEAFCG，后序遍历：DEBFGCA。
接下来我们要解决一个问题咯：用前序遍历或后序遍历和中序遍历求出这棵二叉树（中序遍历是不能少的）
第一步：取出前序遍历第一个字母A，可知A结点是这棵树的父结点（大多数情况都是），再在中序遍历中找到A，可将A左边分为左子树，将A右边分为右子树（E自然是A的右儿子，不管它了）。
第二步：取出前序遍历第二个字母B，可知B是A的左儿子，将B暂时作为根，在中序遍历中找到B，也将B底下的子树划为左子树和右子树，B没有右儿子。
第三步：取出前序遍历第三个字母C，C是B的左儿子，再在中序遍历中把C底下的子树划分一下，发现只剩下一个字母D，则D是C的右儿子。
整体二叉树：
（说明：我只是拿了图过来，没有抄袭文字哦，地址：https://www.cnblogs.com/WindSun/p/10859055.html）
查找到此结束，另外的查找算法大家自行拓展，马上进入下一趴，搜索！
搜索
现在有这样一道题摆在你眼前：
Farmer John有一个农场。一天下雨后，农场上有一些积水（W），当然也有没有积水的地方（.)。现在，
Farmer John想要知道农场里有多少个池塘，例如：
.WW
WW.
上面这样的图是一个池塘，但是：
..WW
WW..
这样的图是两个池塘，输入农场上的积水情况，请问农场里有几个池塘？（默默地打出一个“？”）
你想用刚刚学到的查找来AC这道题，但你发现这好像并不实际，因为你要查找的是一片区域。
这个时候，我们要学习新算法啦，它就是：搜索！
搜索是计算机解题中常用的算法，常常和回溯碰到一起。基本思想是为了求得问题的解，先选择某一种情况往前探索，在过程中一旦发现这种情况碰壁 （职场生存技能），就退回一步重新选择，继续向前探索，如此反复进行，直到得到解或证明无解为止。搜索算法也常常会用递归实现。
接下来我们分类讨论：
深度优先搜索
深度优先搜索就是深搜 （这种术语其实很容易听不明白），我们看一张图：
如图是一个无向图，如果我们从A点开始检索（以下顺序无先后之分），我们先得到这个过程：A->B->E，发现没路，回溯到A，继续搜索过程：A->C->F->H->G->D，发现又没路了，最终回溯到A，搜索结束（每个点都检索过一遍了）。这就是深搜的全过程。
我们常常用深搜实现走迷宫问题，以上的Farmer John数池塘问题也可以概括在内。
那么，我们来实现一个走迷宫的子程序：
int g[100][100];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};//dx和dy数组是表示怎样移动
int n,m;//整个迷宫的行和列
void walk(int x,int y,int dep){
g[x][y]=1;//将所占格设为有障碍，以便后面搜索中不返回这格
if(x==n&&y==m){
cout<<dep<<endl;
return ;//如果到终点，返回上一步，探索更多路线
}
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];//更新tx，ty
if(tx>0&&tx<=n&&ty>0&&ty<=m&&g[tx][ty]==0){
walk(tx,ty);
}//判断是否能走下一步
}
g[x][y]=0;//走不下去，将这格返回原来样子
}根据这个子程序，我们可以实现这个数池塘问题了:
#include<bits/stdc++.h>
using namespace std;
int g[1010][1010],n,m;
int tx[4]={0,0,1,-1};
int ty[4]={1,-1,0,0};
void walk(int dep,int x,int y){
g[x][y]=1;
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>0&&tx<=n&&ty>0&&ty<=m&&g[tx][ty]==0){
walk(tx,ty);
}
}
}
int main(){
int gs=0;
cin>>n>>m;
char ch;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ch;
if(ch=='W'){
g[i][j]=0;
}
else
{
g[i][j]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]==0){
gs++;
walk(0,i,j);
}
}
}
cout<<gs<<endl;
return 0;
}
广度优先搜索
广度优先搜索就是宽搜。与深搜不同，若把深搜基本思想改为深度越小的结点越先得到扩展，就是广度优先搜索。宽搜常常用队列queue实现，这里我们就不得不涉及一些STL了 （编程太难了，我们来学习珂学吧！）：
queue的定义方法是：
//queue+<数据类型>+队列名称；例：
queue <int> q;//<>是不能少的另外，这里有一些特殊队列，不展开细讲，大家可以上网咨询：
deque <int> q;//双端队列
priority_queue <int> q;//优先队列（可以自动排序）关于队列的一些STL命令：
q.push(a);//将a插入到队尾
q.pop();//队首出列
q.empty()//判断队列是否为空
q.front();//队首
q.back();//队尾其它命令大家也可以上网搜~
队列的基本思想：先进先出，这也导致无法从队列中间插入数据 （就像你食堂打饭不能插队，否则食堂大妈会给予你手抖攻击）。
这个时候我们就要来看实例啦，本题是作者原创哦~
关于S博士研究出的这个新数，也是在一种数的基础研发的。它就是丑数。只不过，博士在这个概念的基础
上又增加了一些新的概念。众所周知，丑数是除了1和它本身，只含有素因子2、3、5、7的数（规定1不是
丑数）（其实与真正的丑数稍有不同），就像15是一个丑数，它只含有3和5两个因子，而11却不是丑数，
因为11除了1和11两个因子，无其他素因子。而S博士则更加疯狂，他规定，你需要求出第n个丑数的丑数
（以下简称丑丑数），就是要先求出第n个丑数，而后将第n-2、n+2个丑数和第n个丑数作为丑丑数的
“素因子”，求出只含有第n、n-2、n+2个丑数，也就是“素因子”的最小的数。现在，疯狂的S博
士为了把你难住（虽然这并不现实），想让你求出在2到k的这些数中，有几个n的丑丑数？这题呢大家可能看着也有点熟悉，其实就是在丑数的概念上改编的。如果只要求第n个丑数，我们可以看这样一个程序：
#include<bits/stdc++.h>
using namespace std;
queue<int>q,q1,q2,q3,q4;
int main(){
int n;
cin>>n;
q.push(1);//如果队列一开始没有东西程序是运行不了的！
for(int i=1;i<=n;i++){//由于求第n个丑数，就只要n次循环
q1.push(q.front()*2);
q2.push(q.front()*3);
q3.push(q.front()*5);
q4.push(q.front()*7);//取出答案q队列的队首（肯定只有2、3、5、7因子），再分别乘2、3、5、7放到四个队列里
int minn=min(min(q1.front(),q2.front()),min(q3.front(),q4.front()));//比较最小的一个丑数是哪个，准备放入q队列里
q.pop();//队首出队，已经没用了
q.push(minn);//将当前最小丑数放入q队列
if(q1.front()==minn) q1.pop();
if(q2.front()==minn) q2.pop();
if(q3.front()==minn) q3.pop();
if(q4.front()==minn) q4.pop();//比较是否有minn（四个队列里可能有重复丑数），有则出队
}//每次q队列都进1个，出1个，不会出现q队列中没有数据的时候
cout<<q.front()<<endl;//输出最后答案
return 0;
}显而易见，上题只是要求两次丑数而已，并加上数组存储之术，就可以实现啦 （程序我就不公布了，反正你们交不了题）。
Further Thinking
一个比较popular的词汇……
接下来，我们要拓展一些更有意思的函数：
stack
stack就是指栈，栈的思想与队列不同，是先进后出；向栈中添加/删除数据时，只能从栈顶进行操作。定义如下：
//stack+<数据类型>+栈名称
stack <int> a;基本操作：
a.push(x);//输入
a.pop();//弹出
a.empty();//判断栈是否为空
a.top();//栈顶利用栈，我们可以完成后缀表达式的计算（好高级的感jio），实例不再展开。
vector
在c++中，vector是一个十分有用的容器。它可以容纳许多类型的数据，如若干个整数，所以称其为容器。可以将其视为能够存放任意类型的动态数组。vector 是C++ STL的一个重要成员。定义：
//vector+<数据类型>+名字
vector <int> v;
//vector+<数据类型>+名字+[数组长度]
vector <int> v[1000];在定义的第二种中，是将vector作为二维数组来使用，调用命令时可用v[……].push来使用。当然，单独的vector也可以当作一维数组调用。命令如下：
v.push_back(a);//将a插入到vector的尾部
//对于一个空的vector,不能使用下标向其中添加元素，只能使用push_back.。
v.empty();//检查是否为空
v.capacity();//返回当前vector中最大可以存储数据的容量
v.size();//返回v中元素的个数
v[n];//获取v中第n个元素迭代器（打星星哦）：
vector的输出使用迭代器，定义是：
vector<int>::iterator it;//it是能读写的vector<int>的元素使用实际：
vector<int>::iterator it;
for（it=v.cbegin();it!=v.end();it++）
{
cout<<*it<<endl;
}运用vector，我们可以解决约瑟夫问题哦~
map
map 容器是关联容器的一种。你可以把map理解为一个二维数组，但不同之处在于，二维数组的下标必须是数字，但map不同，很多数据类型都可以放进去。我们通常用字符串作为下标，来保存姓名和地址的记录。
map可表示的是 map<Name，size_t> 类型的容器，定义：
//map+<一种数据类型，另一种数据类型>+名称
map <string,int> m;//如果想要用姓名记录，string必须在前面哦比如说，输入几个字符串，问你相同字符串最大有多少个，你可以这样调用：
//每当扫到一个字符串后，像哈希排序一样统计
输入：Amy
则m["Amy"]++；这样很多问题都可以简单化，比如统计一个人的考试成绩，等等。（顺便问一句你们考试考得好吗）
pair
这是最后一个了！pair可以理解为“一对数据”，就是像一个二元组的东西。如果想将两个数据合成为一个，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。定义：
//pair+<一种数据类型，另一种数据类型>+名称
pair <int,string> p;
//高级一点，pair <int,vector<int>> p也是被认可滴！关于输入，有两种方法：
1、访问两个元素操作可以通过first和sencond访问：
pair<int ,double> p;
p.first = 1;
p.second = 2.5;2、可以利用make_pair创建新的pair对象：
pair<int, string> p;
p = make_pair(1,2.5);（你们喜欢哪一个？我也不清楚）
总之这就是这篇文章的全部内容了！事实证明：STL是个好东西，所以我们来学习珂学吧！
最后一句：这篇文章真的不是浅谈啊！！！