大话数据结构-8.4 有序表查找 - 高飞网

8.4 有序表查找

2016-12-29 22:01:27.0

8.4.1 折半查找

    折半查找(Binary Search)技术,又称为二分查找。它的提前是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等则查找成功;若给定的值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定的值大于中间记录的关键字,则在中间记录的右半区查找。不断重复上述过程,甚至查找成功,或所有查找区域无记录,查找失败为止。

    折半查找代码:

/* 折半查找 */
int Binary_Search(int *a,int n,int key)
{
	int search_count = 0;
	int low = 0,high=n-1;
	int mid = 0;
	do{
		search_count++;
		mid = (low+high)/2;/* 折半 */

		if(key<a[mid])
		{/* 小于mid则在左区查找 */
			high = mid-1;
		}
		else if(key>a[mid])
		{/* 大于mid则在右区查找 */
			low = mid+1 ;
		}
		else
		{
			printf("查找次数:%d次\n",search_count);
			return mid;
		}
	}while(low<=high);/*直到low等于high为止*/
	printf("查找次数%d:\n",search_count);
	return -1;
}

   输出如下:

数组为:6,12,18,25,31,37,43,50,56,62,68,75,82,88,96,
查找次数:4次
43在数组的第6位

    那折半查找的效率有多高呢?首先,将查找过程绘制成一棵二叉树,之前说过二叉树性质4:“具有n个结点的完全二叉树的深度为 [log2n]+1 ”,尽管折半查找判断二叉树并不是完全二叉树,但同样相同的推导可以得出,最坏情况是查找到关键字或查找失败的次数为 [log2n]+1,最终时间复杂度为:O(logn)

    折半查找的前提条件是需要有序表顺序存储,对于静态查找表一次排序不再变化,这样的算法比较好。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序带来不小的工作量,就不建议使用了。

8.4.2 插值查找

    例:如果想在字典查询"zoo",肯定不会先从中间查,再依次折半,正确的方式是直接翻到后面查;

    例:如果在0~10000之间的100个元素从小到大均匀分布的数组,查找5,肯定会从较小的开始查找。

    因此,折半查找,还是有改进空间的。

    折半查找的代码折半算法:mid=(low+high)/2;还有改进空间。可以进行如下的变换:



    即将1/2变为。下面是代码:

/* 插值查找算法 */
int InterpolationSearch(int *a,int n,int key)
{
	int search_count = 0;
	int low = 0,high=n-1;
	int mid = 0;
	do{
		search_count++;
		mid = low + (high-low)*(key-a[low])/(a[high]-a[low]);/* 插值 */
		if(key<a[mid])
		{/* 小于mid则在左区查找 */
			high = mid-1;
		}
		else if(key>a[mid])
		{/* 大于mid则在右区查找 */
			low = mid +1;
		}
		else
		{
			printf("查找次数:%d次\n",search_count);
			return mid;
		}
	}while(low<=high);/*直到low等于high为止*/
	printf("查找次数%d:\n",search_count);
	return -1;
}

输出为:

数组为:6,12,18,25,31,37,43,50,56,62,68,75,82,88,96,
查找次数:2次
43在数组的第6位

    可见只用了2次就查找到结果了,显然大大提高了查找效率。

    插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后查找方法,其核心在于插值计算公式

    虽然时间复杂度都是O(logn),但对于表长较大,而关键字分布比较均匀的查找表来说,插值查找算法的平均性能比较折半查找要好得多。但比如分布不均匀的数据,就不合适了。

8.4.3 斐波那契查找

    斐波那契查找(Fibonacci Search),它复用了黄金分割原理来实现的。

/* 斐波那契查找 */
int Finbonacii_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;
}

    也就是说,如果要查找的记录在右侧,则左侧的数据不用再判断了,不断反复进行进去,对处于当中的大部分数据,其工作效率要高一些。所以尽管斐波那契查找的时间复杂度也为O(logn),但就平均性能来说,斐波那契查找要优于折半查找。

    折半查找(mid=(low+high)/2),插值查找(mid=low+(high-low)*(key-a[low])/(a[high]-a[low])),斐波那契查找(mid=low+F[k-1]-1),本质区别在于分隔的选择不同,各有优劣。