顺序查找和折半查找（代码实现）

妖狐艹你老母 2022-12-27 09:00 151阅读 0赞

## 顺序查找 ##

这个查找比较简单，就是单纯的比较数据，如果相等就是查找成功，但是对于数据量大的数据，效率会非常的低。直接上代码

//顺序查找算法 
    int Search(Table table , int key){
        
    	table.elem[0] = key;
    	int i;
    	for(i = table.length-1;table.elem[i] != key;--i);
    	return i;
    }

下面是顺序查找的优化算法（基于顺序表的顺序查找适用）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70]当我们用上面的结构进行查找的话，我们会发现一个神奇是事情，当我们进行查找的时候，查找到数据为十三的时候，下一个数据是6，因为这个表是顺序表，那么我们就判定，下面不会再有跟key匹配的数据，那么我们就可以将查找过程就此打住，结束查找，判定查找失败。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70 1]以上就是顺序查找的全部内容，我的测试代码是使用数组实现的，链表也同样可以实现。

## 折半查找 ##

查找算法中的主角，但是有一个很大的局限性，只适用与有序表的查找。算法的思想也不算难。简单来说就是判断使用mid将数组中的元素分为两部分，判断key值可能会出现的区间，不断的重复，直到某个条件成立或者查找失败，结束递归。  
先上代码

int Binary_search(Table table,int key)
    {
        
    	int low=1,high=table.length,mid;
    	while(low<high){
        
    		mid = (low+high)/2;
    		if(table.elem[mid] == key){
        
    			return mid;
    		}else if(table.elem[mid]<key){
        
    			low = mid + 1;
    		}else{
        
    			high = mid-1;
    		}
    	}
    	return 0;
    }

我们用二叉树的形态来表达顺序表被分割的状态。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70 2]看着上面图像进行比较，我想应该能够快速理解算法的思想。  
下面说一下注意事项:  
1.算法结束的标志，代码中规定的low，high指针代表的就是每一个区间中的数据最大下标和最小下标，当最下下标大于最大下标的时候，我们就递归，此时就是查找失败的条件，也就是递归的出口。  
2.由于折半查找需要大量的随机访问数据，所以并不适用与链表存储的数据，只适用有序的顺序表。  
3.折半查找的最大比较次数不会比树的高度大。

总代码：（这次没有写太多的注释，有什么不懂的或者错误的地方，都可以在下面评论，看到就会回复的）

#include <iostream>
    using namespace std;
    //数据存储结构
    typedef struct {
        
    	int *elem;
    	int length;
    }Table; 
    //顺序查找算法 
    int Search(Table table , int key){
        
    	table.elem[0] = key;
    	int i;
    	for(i = table.length-1;table.elem[i] != key;--i);
    	return i;
    }
    //有序表的优化顺序查找算法
    int Opt_Search(Table table , int key){
        
    	table.elem[0] = key;
    	int i;
    	for(i = table.length-1;table.elem[i] != key;--i){
        
    		if(table.elem[i-1]<key){
        
    		i=0;
    		break;
    	}
    	}
    	return i;
    }
    
    //折半查找 
    int Binary_search(Table table,int key)
    {
        
    	int low=1,high=table.length,mid;
    	while(low<high){
        
    		mid = (low+high)/2;
    		if(table.elem[mid] == key){
        
    			return mid;
    		}else if(table.elem[mid]<key){
        
    			low = mid + 1;
    		}else{
        
    			high = mid-1;
    		}
    	}
    	return 0;
    }
    int main ()
    {
        
    	Table T ;
    	int a[10] = {
        0,1,2,3,4,5,6,7,8,9};   //0是为哨兵所留位置 (节省判断数组下标越界的代码的方法)
    	T.elem = a;
    	T.length = sizeof(a)/sizeof(int);
    	if(Search(T,5) == 0)
    	cout<<"查找失败！"<<endl;
    	else
    	cout<<Search(T,5)<<endl;
    	if(Binary_search(T,6) == 0 )
    	cout<<"查找失败！"<<endl;
    	else
    	cout<<Binary_search(T,6)<<endl;
    	cout<<Opt_Search(T,5)<<endl;
    	return 0;
     }

按照上面的逻辑，我们也可以将数组进行多次的分块，也就是分块查找（索引查找）的概念，块内元素可以无序，因为在块内我们是使用顺序查找算法进行比较的，但是块间的元素必须有序，也就是说，第二个块中的元素的最大数据必须小于第三块中的元素的最小值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70]: /images/20221120/e7f72a2297bc44a4b39a1b5b322fa87b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70 1]: /images/20221120/da50bb190b0f4abfbe887e533c7e4abf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70 2]: /images/20221120/5ba890cd0f984deb96755c4e3fb3a008.png