数据结构26————有序表查找

曾经终败给现在 2022-05-28 12:06 208阅读 0赞

# 数据结构23————有序表查找 #

### 一. 目录 ###

### 文章目录 ###

*  数据结构23————有序表查找
 *   *   *  一. 目录
         *  二. 有序表查找
         *  三. 二分(折半)查找
         *   *  1. 思路
             *  2.代码
             *  3.时间复杂度
         *  四. 插值查找
         *   *  1.产生原因
             *  2.思路
             *  3.代码
         *  五. 斐波那契查找
         *   *  1.思路
             *  2.代码
             *  3.性能优越
         *  六. 参考资料

### 二. 有序表查找 ###

有序表查找即在一个有序表中查找需要的值，因为是有序的所以可以不用如线性表那样遍历所有数据，可以利用有序这一特点进行查找。

### 三. 二分(折半)查找 ###

#### 1. 思路 ####

> 在有序表(从小到大)中，取中间记录作为比较对象,若给定值与中间记录的关键字相等，则查找成功，如给定值小于中间记录的关键字，则在中间记录的左半区继续查找,若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。

#### 2.代码 ####

#include <stdio.h>
    //二分查找, a为查找的数组(数组从1开始存储)，n为数组长度,key为要查找的关键字
    int Binary_Search(int *a,int n,int key){
        
    	int low,high,mid;
    	low = 1;
    	high = n;
    	while(low <= high){
        
    		mid=(low + high)/2;
    		if(key < a[mid]){
        
    			high = mid-1;
    		}else if(key == a[mid]){
        
    			return mid;
    		}else if(key > a[mid]){
        
    			low = mid+1;
    		}
    	}
    	return 0;
    }

#### 3.时间复杂度 ####

对于一个有n个数据有序数组，最好的情况下查找次数:1次，最坏的情况下查找次数 \[ l o g 2 n \] + 1 \[log\_\{2\} n\]+1 \[log2n\]\+1， 所以二分查找的时间复杂度为 O \[ l o g n \] O\[logn\] O\[logn\]

### 四. 插值查找 ###

#### 1.产生原因 ####

在有些时候，二分查找时每次和最中间的相比，并不是最优的情况，比如说在均匀分布1-100的有序数组中查找5，我们自然会考虑从下标比较小的开始查找。所以在这种情况下，二分查找依然有改进的空间

#### 2.思路 ####

> 插值查找是根据要查找的关键字key和查找表中的最大最小记录的关键字比较后的查找方法，其核心公式是$ \\frac\{key-a\[low\]\}\{a\[high\]-a\[low\]\}  , 即 每 次 将 给 定 值 与 下 标 为 ,即每次将给定值与下标为 ,即每次将给定值与下标为 \\frac\{key-a\[low\]\}\{a\[high\]-a\[low\]\} $的值进行比较

#### 3.代码 ####

总体和二分查找差不多，不过将mid = （low+high）/2改为:mid = low +(high - low)\*（key-a\[low\]）/(a\[high\]-a\[low\])

### 五. 斐波那契查找 ###

对于二分查找的改进除了插值查找外，还有一种，即斐波那契查找。

#### 1.思路 ####

> 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=Fk-1(不足补齐) ， F(K)为斐波那契数列。即\{0,1,1,2,3,5,8,13…\}  
> 核心思路：  
> 开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种:

1.  相等，mid位置的元素即为所求
2.  大于 ,low=mid+1,k-=2; 即：查找的元素在\[mid+1,hign\]范围内，元素个数为F(k-2)-1个
3.  小于,high=mid-1,k-=1; 即：查找的元素在\[\[low,mid-1\]\]范围内，元素个数为F(k-2)-1个  
    ![这里写图片描述][70]

#### 2.代码 ####

int Fibonacci_SEarch(int *a,int n,int key){
        
    	int low,high,mid,i,k;
    	low = 1;  // 定义最低下标的记录首位 
    	high = n;  //定义最高下标为记录末尾 
    	k=0;  
    	while( n>F[k]-1){
         //计算n位于斐波那契数列的位置 
    		k++;	
    	}
    	for(i=n;i<F[k]-1;i++){
         //将不满的数值补全 
    		a[i] = a[n];
    	}
    	
    	while(low <= high){
        
    		
    		mid = low + F[k-1] -1;//计算当前分割的下标 
    		
    		if( key <a [mid]){
         //若查找记录小于当前分割记录 
    			high = mid -1; //最高下标调整到分割下标mid-1处 
    			k=k-1; //斐波那契数列下标减一位 
    		}else if(key > a[mid]){
        //若查找记录大于当前分割记录 
    			low = mid +1;//最高位下标调整   到分隔符下标mid+1处 
    			k=k-2;//斐波那契数列减两位 
    		}else{
        
    			if(mid<=n){
        
    				return mid; //若相等则说明mid即为查找到的位置 
    			}else{
        
    				return n; // 若mid>n说明是补全数组，返回n 
    			}
    		} 
    	}
    	return 0;
    }

#### 3.性能优越 ####

关于斐波那契查找， 如果要查找的记录在右侧，则左侧的数据都不用再判断了，不断反复进行下去，对处于当众的大部分数据，其工作效率要高一些。所以尽管斐波那契查找的时间复杂度也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。可惜如果是最坏的情况，比如这里key=1，那么始终都处于左侧在查找，则查找效率低于折半查找。

还有关键一点，折半查找是进行加法与除法运算的（mid=(low+high)/2），插值查找则进行更复杂的四则运算（mid = low + (high - low) \* ((key - a\[low\]) / (a\[high\] - a\[low\]))），而斐波那契查找只进行最简单的加减法运算（mid = low + F\[k-1\] - 1），在海量数据的查找过程中，这种细微的差别可能会影响最终的效率。

### 六. 参考资料 ###

《大话数据》  
《数据结构与算法》

[70]: /images/20220528/b094dee29d104f3aa624e3b13b55db0b.png