寒假之搜索（不是dfs/bfs）

本文主要是介绍寒假之搜索（不是dfs/bfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性搜索 二分搜索 借助STL标准库 进行搜索

1.线性搜索听名字就是以线的方式来遍历，直接从头到尾开始遍历，找到就找到，找不到就找不到。复杂度是O(n)。主要有两种方式来实现。

a：

bool linesearch(int *a,int num,int n)
{int i=0;a[n]=num;while(a[i]!=num)i++;if(i==n)return false;   //没有找到 return true;   		//找到了 
}

b:

bool linesearch(int *a,int num,int n)
{int i=0;for(i=0;i<=n;i++){if(a[i]==num){return false;}} return false;
}

2.二分搜索，复杂度为O( log(n) ),在一些数据量大的时候，可以用二分搜索。

bool binary(int laft,int right,int num)
{paixu();  //需要先排序,可以用一下 sort while(left<right){int mid=(left+right)/2;if(a[mid]==num)return true;else if(a[mid]>num)right=mid;else if(a[mid]<num)left=mid+1;}return false;
}

 二分搜索在一些题目上，有很多的变形，例如二分答案（二分加贪心的升级问题），对于区间的把握程度有很大的要求，需要多练习相关的题目，我下面讲讲具体的怎么处理问题的。

1.在大数据的情况下查找满足条件的数（前提是数据都是有序的），将区间一分为二，先判断中间值与查找数之间的大小关系，在左边那就继续在左边查找，在右边就相反操作。在不断的查找过程中，left 和 right  都是在不断的更新，当left 和 right 相等或者 left 大于 right 时，这时就不能再一分为二了。如果还没有查找到，就是真的没有；在二分的过程中，如果找到，就直接 return  掉。 这个left 和 right 如何变 根据题目的要求。

2.二分答案题型,属于难度提高题目，常常与贪心一起出现，不是仅仅二分数据，而是不断二分满足的答案，直到找到满足最优解的答案。（比如两者之间尽可能小的（间距）最大值或者最小值），这就要先满足 1 条件（尽可能小），然后再满足的二个条件是最大值和最小值 。这个就是二分答案，在不断的二分答案，找到最优的解。通常二分与很多算法都在一起使用，比如贪心等算法。就在二分过程当中判断此时答案是否符合标准，再进一步优化找到最优解。

POJ 2456 3273 2976 3122 1505 2018 HDU 5248 4004  2899 1969 4334 6383  洛谷1182 1824 noip 2012  CF 923B  

部分二分答案习题，自己可以练习。

 

看道例题：

 

给你一个n个整数序列和一个不同的q个整数序列t。写一个程序，输出c，t中的整数个数，也在集合s中。 

输入              

在第一行给出n。在第二行中，给出n个整数。第三行中给出了q。然后，在第四行中，给出q整数。

输出              

在一行中输出c。

约束条件              

s中的元素按升序排序

• n ≤ 100000
• q ≤ 50000
• 0 ≤ an element in S ≤ 109
• 0 ≤ an element in T ≤ 109
• Sample Input 1

• 5
  1 2 3 4 5
  3
  3 4 1

  Sample Output 1

  3

  Sample Input 2

  3
  1 2 3
  1
  5

  Sample Output 2

  0

  Sample Input 3

  5
  1 1 2 2 3
  2
  1 2

  Sample Output 3

  2

二分算法：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<set>
const int maxn=100005;
typedef long long ll;
bool erfen(ll *a,ll left,ll right,ll num)
{while(left<right){ll mid=(left+right)/2;if(num==a[mid])return true;else if(num<a[mid])right=mid;else if(num>a[mid])left=mid+1;}return false;
}
int main()
{ll num;ll a[maxn];ll i;ll n;ll k=0;cin>>n;for(i=0;i<n;i++)cin>>a[i];sort(a,a+n);ll q;cin>>q;for(i=0;i<q;i++){cin>>num;if(erfen(a,0,n,num))k++;}cout<<k<<endl;return 0;
}

用到STL 问题就相对于简单一点（其实一样）

下面看一个用一个 lower_bound 来实现：

代码：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<set>
const int maxn=100005;
typedef long long ll;
int main()
{ll k=0;ll i;ll a[maxn];ll n,q;cin>>n;for(i=0;i<n;i++)cin>>a[i];cin>>q;for(i=0;i<q;i++){ll num;cin>>num;ll pos=lower_bound(a,a+n,num)-a;if(a[pos]==num)k++;}cout<<k<<endl;return 0;
}

 下面就用一个 set 就可以实现，代码：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<set>
const int maxn=2000005;
typedef long long ll;
int main()
{ll k=0;ll num;int i;set<ll>s1;set<ll>s2;set<ll>::iterator it=s2.begin();int n,q;cin>>n;for(i=0;i<n;i++){cin>>num;s1.insert(num);}cin>>q;for(i=0;i<q;i++){cin>>num;s2.insert(num);}for(it=s2.begin();it!=s2.end();it++){if(s1.find(*it)!=s1.end())k++;}cout<<k<<endl;return 0;
}

简单说的说一下原理吧，先将 是数组排序（必要条件）否则二分不能实现，就是每次将区间分一半，在左边的话，就抛弃右边；在右边，就抛弃左边。大大的减少了时间。、

3.有的搜索就可以直接用STL实现，（比如一些set vector 有一些搜索的函数 find()  ),就可以直接套用。

看看题：

您的任务是编写一个简单字典程序，该程序实现以下指令：              

您的任务是编写一个简单字典程序，该程序实现以下指令：              

insert str：在字典中插入字符串str              

查找str：如果distinary包含str，则打印“yes”，否则打印“no”              

输入              

在第一行n中，给出了指令数。在以下n行中，n条指令以上述格式给出。              

产量              

对一行中的每个查找指令打印“是”或“否”。              

约束条件              

字符串由“a”、“c”、“g”或“t”组成              

1≤字符串长度≤12              

n＝1000000 

代码：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<string>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<list>
#include<set>
const int maxn=100005;
typedef long long ll;
int main()
{char zifu[20];char zhiling[20];ll t;cin>>t;set<string>s;while(t--){cin>>zhiling>>zifu;if(zhiling[0]=='i'){s.insert(zifu);}else if(zhiling[0]=='f'){if(s.find(zifu)!=s.end())cout<<"yes"<<endl;else cout<<"no"<<endl;	}	}return 0;
}

这些 stl 的用法，应该要掌握，不了解的，可以看看博客学习一下。

 

 

 

 

 

这篇关于寒假之搜索（不是dfs/bfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---