《大话数据结构》之分段查找

深藏阁楼爱情的钟 2022-08-18 02:54 111阅读 0赞

我所谓的分段查找包括：二分查找、插值查找、Fibonacci查找。

三者都是不断的缩小查找范围的查找方法，只是在每次缩小多少范围上有所区别。

二分查找：

最简单，每次一刀切，切一半，相对于其他两种方法显得很笼统，但是适配性不错，没有特殊限制。

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;
    		}
    	}
    	return 0;
    }

插值查找：

如果查找的数据分布呈等差数列，那么这种方式会比较好。

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;
    		}
    	}
    	return 0;
    }

特色在于如何计算中间值。他假设所有数据都是等值分布的，和他们的下标是成比例的，所以才会计算，目标值占最大和最小值的差值的比例，并乘以下标差。

Fibonacci查找：

这个查找不在做任何假设，他利用了Fibonacci数列的相邻两个值在不断扩大的特性，来先大后小的不断缩减查找范围。

代码中求中值用到了Fibonacci数列的F\[k\] = F\[k-1\] + F\[k-2\]的特色。

/*
    借用Fibonacci数列逐步递增范围的特性，来划分查找的范围
    */
    int Fibonacci_Search(int *a,int n,int key)
    {
    	int low,high,mid,i,k;
    	low = 1;
    	high = n;
    	k = 0;
    	/*
    	F是计算好的Fibonacci数组
    	*/
    	while(n>F[k]-1)
    	{
    		k++;
    	}
    
    	for(i=n;i<F[k]-1;i++)
    	{
    		a[i] = a[n];
    	}
    	
    	/*与二分查找类似，但是增量和减量借助了Fibonacci数列，不再是等值的*/
    	while(low <= high)
    	{
    		/*
    		每次查找的切分的范围
    		*/
    		mid = low + (F[k-1] - 1);
    		/*
    		整个数据个数是F[k]个，F[k]=F[k-1]+F[k-2]
    		此处是以F[k-1]为切分位置，移动high，实际上此时只剩下F[k-1]个值
    		F[k-1]=F[k-2]+F[k-3]，又因为计算mid时，k要减一，所以就是(k-1)=k-2，可知此时的k=k-1
    		*/
    		if(key<a[mid])
    		{
    			high = mid - 1;
    			k = k - 1;
    		}
    		/*
    		此处将low上移，也就是只取F[k-2]个值，因为F[k-2]=F[k-3]+F[k-4]
    		而且计算mid时，k要减一，所以就是(k-1)=k-3，所以k=k-2
    		*/
    		else if(key > a[mid])
    		{
    			low = mid + 1;
    			k = k - 2;
    		}
    		/*key == a[mid]*/
    		else
    		{
    			/*
    			因为后面有补充的值
    			*/
    			if(mid <= n)
    			{
    				return mid;
    			}
    			else
    			{
    				return n;
    			}
    		}
    	}
    	return 0;
    }

难点在于如何理解，high = mid - 1时，k = k -1；而low = mid + 1时，k = k - 2。

关键在于还剩多少，排除在查找范围外的有多少，理清了这个，也就搞清楚了为什么high = mid - 1时，k = k -1；而low = mid + 1时，k = k - 2了。