搜索问题

今天药忘吃喽~ 2022-12-03 09:30 108阅读 0赞

搜索是指从数据集合中找出目标元素的处理，与排序相同，搜索的各元素通常也由多个项目组成。  
本篇例题：从长为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)