【数据结构】有序表查找及实现

朱雀 2022-12-11 07:45 114阅读 0赞

## 折半查找 ##

折半查找（Binary Search），又称为二分查找。它的前提就是U是线性表中的记录必须有序的，线性表必须采用顺序存储。  
**折半查找的基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大雨中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。**

/* 折半查找 */
    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])/* 若查找值比中值大 */
    			low=mid+1;		/* 最低下标调整到中位下标大一位 */
    		else
    		{
        
    			return mid;		/* 若相等则说明mid即为查找到的位置 */
    		}
    		
    	}
    	return 0;
    }

该算法还是比较容易理解的，假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。  
最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素  
令n/2^k=1，  
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn).

## 插值查找 ##

**插值查找是根据要查找的关键字key与查找表汇总的最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式**  
![在这里插入图片描述][2020092912482544.png_pic_center]  
应该说从时间复杂度来看，他也是O(logn)，但对于表长比较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均I性能比折半查找要好的多。

/* 插值查找 */
    int Interpolation_Search(int *a,int n,int key)
    {
        
    	int low,high,mid;
    	low=1;	/* 定义最低下标为记录首位 */
    	high=n;	/* 定义最高下标为记录末位 */
    	while(low<=high)
    	{
        
    		mid=low+ (high-low)*(key-a[low])/(a[high]-a[low]); /* 插值 */
    		if (key<a[mid])		/* 若查找值比插值小 */
    			high=mid-1;		/* 最高下标调整到插值下标小一位 */
    		else if (key>a[mid])/* 若查找值比插值大 */
    			low=mid+1;		/* 最低下标调整到插值下标大一位 */
    		else
    			return mid;		/* 若相等则说明mid即为查找到的位置 */
    	}
    	return 0;
    }

## 裴波纳契查找 ##

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;

开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

1）相等，mid位置的元素即为所求

2）> ,low=mid+1,k-=2;说明:low=mid+1说明待查找的元素在\[mid+1,hign\]范围内，k-=2 说明范围\[mid+1,high\]内的元素个数为n-（F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找

3)< ,high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在\[low,mid-1\]范围内，k-=1 说明范围\[low,mid-1\]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找

同样，斐波那契查找的时间复杂度还是O(log 2 n )，但是 与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

/* 斐波那契查找 */
    int Fibonacci_Search(int *a,int n,int key)
    {
        
    	int low,high,mid,i,k=0;
    	low=1;	/* 定义最低下标为记录首位 */
    	high=n;	/* 定义最高下标为记录末位 */
    	while(n>F[k]-1)
    		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;		
    			k=k-1;
    		}
    		else if (key>a[mid])
    		{
        
    			low=mid+1;		
    			k=k-2;
    		}
    		else
    		{
        
    			if (mid<=n)
    				return mid;		/* 若相等则说明mid即为查找到的位置 */
    			else 
    				return n;
    		}
    		
    	}
    	return 0;
    }

[2020092912482544.png_pic_center]: /images/20221123/8bcd6dc05bc949529fd96399647c6ffc.png