【数据结构周周练】026 折半查找算法及与顺序查找算法对比分析

男娘i 2021-06-11 15:13 424阅读 0赞

# 一、前言 #

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

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

# 二、折半查找 #

## 1、折半查找概念 ##

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

查找过程如下：

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

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

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

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

## 2、示例及代码 ##

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

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

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

#include<iostream>
    #include<malloc.h>
    
    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、实现效果 ##

![20181107215734140.png][]

![20181107215838311.png][]

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

## 1、回顾ASL ##

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

![2018110721064834.png][]

## 2、顺序查找ASL ##

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

![20181107220547330.png][]

## 3、折半查找ASL ##

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

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

![20181107222800802.png][]

且有

![20181107224234512.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][]

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

![20181107225057207.png][]

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

![20181107225420731.png][]

## 4、对比 ##

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

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

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

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

[025]: https://mp.csdn.net/postedit/83831179
[20181107215734140.png]: /images/20210516/da71277fff2746d9820e7ed40bd01c44.png
[20181107215838311.png]: /images/20210516/cf733f5416b645fd9dce4962461c3f9f.png
[2018110721064834.png]: /images/20210516/6107dd31411c43448b8a6b15f17b5efb.png
[20181107220547330.png]: /images/20210516/11212effed984bf8bcb1072ce5c5ce1f.png
[20181107222800802.png]: /images/20210516/6ec7bd3661c3441d97cc0610089ce06c.png
[20181107224234512.png]: /images/20210516/9607c8e8ca1b48c394eda579ddd81295.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/953be1f6d534442c9b1861a28f1e4a04.png
[20181107225057207.png]: /images/20210516/e0b54a9fb88d473cb722417d985f6cab.png
[20181107225420731.png]: /images/20210516/e9418a8503fe4914bc8517d56eaa38c9.png