搜索问题

搜索是指从数据集合中找出目标元素的处理，与排序相同，搜索的各元素通常也由多个项目组成。 本篇例题：从长为N一组数组中找出特定的数M，输出M所在的下标，若没找到该数请输出-1 例如输入： 8 7 1 2 4 6 7 8 5 3 输出：4

线性搜索

线性搜索就是从数组开头开始顺次访问各元素，检查该元素是否与目标值相等。一旦相等则返回该元素的位置并结束搜索。如果检查到数组末尾仍未发现目标值，则返回一个特殊值来说明结果。线性搜索的算法效率很低，但适用与任何形式的数据 代码

#include<iostream> #define MAXN 10000 using namespace std; int a[MAXN]; int search(int N,int M){ int i = 0; while(a[i] != M){ i++; } return i == N-1 ? -1 : i; } int main(){ int N,M; cin>>N>>M; for(int i = 0;i < N;++i){ cin>>a[i]; } cout<<search(N,M)<<endl; return 0; }

线性搜索的算法复杂度未O(n)，但在引入标记之后效率能提升常数倍，处理大规模数据时会有比较明显的效果。

二分搜索

要点 在二分搜索中，我们需要两个标志：left表示搜索的起点，right表示搜索的终点，之后根据left和right的中间值mid与目标数key的比较来移动终点或起点。若mid>key则代表key在mid的左边，那么我们就需要移动终点到mid处缩小区间，反之亦然。但是需要注意的一点是，二分搜索一定要建立在数组有序的前提上，所以我们将例题稍微改动一下，若找到key则输出"找到了"，反之输出"没找到"，并且在搜索中加入排序操作。 代码

#include<iostream> #define MAXN 10000 using namespace std; int a[MAXN]; void insertion(int N){ for(int i = 1;i < N;++i){ int v = a[i]; int j = i - 1; while(j >= 0 && a[j] > v){ a[j+1] = a[j]; j--; } a[j+1] = v; } } int search(int N,int M){ insertion(N); //进行排序 int left = 0,right = N; while(left < right){ int mid = (left + right)/2; if(a[mid] == M) return mid; else if(a[mid] > M) right = mid; else if(a[mid] < M) left = mid + 1; } return -1; } int main(){ int N,M; cin>>N>>M; for(int i = 0;i < N;++i){ cin>>a[i]; } search(N,M) == -1 ? cout<<"未找到"<<endl : cout<<"找到了"<<endl; return 0; }

二分搜索的计算效率为O(logn)