一、前言

上一篇博客讲了有关于查找的概念及顺序查找算法，这次我们再讲解一种新的静态查找算法，大家还记得什么是静态查找吗？相信大家应该记得，如果大家印象不太深刻，可以看一下上一篇博客：。简单说，静态查找就是只查找，不修改。上次我们说适合静态查找的有顺序查找和折半查找等，今天就给大家讲述一下折半查找。

细心的小伙伴们发现了，我在讲顺序查找的博客中并没有讲到顺序查找的ASL，因为我要放在这篇博客中与折半查找做对比，这样，大家才能印象更加深刻。

二、折半查找

1、折半查找概念

折半查找也称二分查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

查找过程如下：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；

否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

再次强调：折半查找在提升查找效率的同时，也对数据的要求有所提高：1.必须采用顺序存储结构。2.必须按关键字大小有序排列。

2、示例及代码

给定一组数据，数据内容如下：

numData[] = { 12,31,45,57,60,71,87,92 };

用户指定查询内容，判断该组数据中是否有用户指定数据。算法实现如下：

#include
   
    #include
    
     using namespace std;int numData[] = { 12,31,45,57,60,71,87,92 };int length = sizeof(numData) / sizeof(int);int SequentialSearch(int numData[],int searchElem) {	for (int i = 0; i < length; i++)	{		if (numData[i] == searchElem)			return i;	}	return -1;}int BinarySearch(int numData[], int searchElem) {	int small = 0;	int large = length-1;	int middle;	if (searchElem > numData[large] || searchElem < numData[0])		return -1;	while (small <= large)	{		middle = (small + large) / 2;		if (searchElem == numData[middle])			return middle;		else if (searchElem > numData[middle])			small = middle + 1;		else			large = middle - 1;	}	return -1;}void main() {	int se;	cout << "Please input the data that you want to inquire : ";	cin >> se;	int k;	//k = SequentialSearch(numData, se);	k = BinarySearch(numData, se);	if (k == -1)		cout << "There is no data that you want to query in this array. " << endl;	else		cout << "The number of the data that you inquiring is : " << k << endl;}

3、实现效果

三、折半查找与顺序查找算法对比分析

1、回顾ASL

大家还记得什么是ASL 吗？对！ASL就是平均查找长度。公式定义如下：

2、顺序查找ASL

首先给大家讲的是顺序查找，顺序查找，我们从第一个元素开始找起，找到我们要找的元素停止，由于可能该元素在数据中的每一个位置，包括最后一个，所以，我们查询可能的次数为：1，2，3，……，n。每次查询的概率为 1 / n 。所以顺序查找的ASL为：

3、折半查找ASL

接下来给大家讲的是折半查找，我们从中间元素开始找起，如果该元素小于我们要查找的元素，则从右边开始查找，如果该元素大于我们要查找的元素，从左边开始查找，直到找到或者全部找完为止。

折半查找过程中，按照其查找流程，会生成如下的判定树，由于该判定树每个结点的左右结点个数差1或0，所以该判定树一定为平衡二叉树。假设判定树有n个结点，则树的深度为k。k的取值如下：

且有

通过分析该判定树，我们可以知道，层次为1的结点有2^(1-1)个，层次为2的结点有2^(2-1)个，……，层次为k的结点有2^(k-1)个，所以，我们可以求得ASL的值为：

当n的值较大（n > 50）时，可有下列近似结果：

4、对比

对比我们从两方面：一方面是查找速度，另一方面是对数据的要求。

在查找速度方面，顺序查找自然是不及折半查找，我们代码中数组的长度比较小，没有太大差距，当数据量较大时，我们就能明显感觉到运行时间差距了。

从另一方面来说，顺序查找对数据要求不高，无需数据按照某种方式排列，也无需指定存储格式，顺序存储可以，链式存储也可以。所以从应用范围来说，顺序查找算法自然会更好。

下一篇博客，我们会给大家讲到另外一种查找方式，这种方式会吸收顺序查找和折半查找的优点。这篇博客就给大家分享到这里啦，有什么问题，大家可以给我留言哦！

转载地址：http://gdyni.baihongyu.com/

你可能感兴趣的文章