作者：解学武

在数据结构中，数据之间的逻辑关系归纳为 4 种，分别是无关系、“一对一”、“一对多”和“多对多”。

通过前面章节的学习，我们掌握了用线性结构（线性表）存储“一对一”关系的数据，用树结构存储“一对多”关系的数据，用图结构存储“多对多”关系的数据。那么，该如何存储无逻辑关系的数据呢？

图 1 中的元素 1、2、3 和 4 之间就不存在任何逻辑关系，增加一个新元素或者删除一个元素，其它元素不会受到影响。

日常工作和生活中，无逻辑关系的数据是最常见的。例如，电话簿中的电话号之间不存在任何逻辑关系，字典中的汉字之间也不存在逻辑关系，数据库表中存储的记录之间也不存在逻辑关系。

数据结构中，将存储无逻辑关系数据的结构称为查找表。

查找表是什么

查找表是一种存储结构，专门用来存储无逻辑关系的数据。也可以这样理解，查找表就是一个包含众多元素的集合，表中的各个元素独立存在，之间没有任何关系。

对于无逻辑关系的数据，做的最多的操作就是从中查找某个特定的元素。和有逻辑关系的数据相比，在无逻辑关系的数据中查找特定元素的难度更大。例如，同样是查找一个电话号，在杂乱无章的电话簿中查找既费时又费力，在有序的电话簿中很快就能找到。

原本没有逻辑关系的数据，为了提高查找效率，会人为地给数据赋予一种逻辑关系，继而选用线性表、树或者图结构来存储数据。比如说，为电话簿中的电话号赋予“一对一”的关系，就可以用线性表（顺序表或者单链表）存储电话号。

从名称上看，查找表是一种新的存储结构，但实际上它指的就是用线性表、树或者图结构来存储数据，只不过数据间的逻辑关系是人为赋予的。

数据结构中，将存储无逻辑关系数据的线性表、树或者图结构统称为查找表。

查找表的分类

在查找表中查找特定的元素，常见的操作有以下几种：

1. 查找特定元素是否在查找表中；
2. 获取（读取）查找表中某个元素的值；
3. 查找失败时，将目标元素插入到查找表中；
4. 查找成功时，将目标元素从查找表中删除。

如果只对查找表做前两种操作，不改变查找表的存储结构，这样的查找表称为静态查找表；反之，如果对查找表做插入或者删除操作，查找表的结构发生了改变，这样的查找表称为动态查找表。

动态查找表可以在查找过程中动态建立，而静态查找表只能先建立然后再执行查找操作。

查找算法的性能分析

用不同的存储结构表示查找表，查找特定元素使用的算法会有所区别。哪怕在同一个查找表中，也可以选用不同的查找算法。

一个算法的好坏，可以从时间复杂度和空间复杂度两个维度衡量。对于查找算法来说，查找过程中只需要极少量的辅助存储空间，所以各个查找算法的空间复杂度区别不大。多数情况下，我们通过时间复杂度衡量查找算法的好坏。

除了时间复杂度之外，还有一种衡量查找算法好坏的方法。

几乎所有的查找算法执行过程中只做一件事，就是将表中元素逐一和目标元素做比较，因此比较次数的平均值（又称平均查找长度，简称 ASL）可以作为衡量查找算法好坏的依据。

一个查找算法的平均查找长度，可以借助下面的数学公式计算出来：

对公式的说明：

• n：查找表中的元素数量；
• P_i：找到第 i 个元素的概率，默认情况下表中各个元素被查找到的概率是相同的，为1/n。在某些特殊场景下，可能会指定表中各个元素被查找到的概率。
• C_i：和第 i 个元素比较后，算法比较过的总次数。比如第 1 个元素首次和目标元素做比较，那么 C₁=1。 

ASL 值越大，表明查找算法的性能越差，执行效率越低。

接下来，我会系统讲解多种查找算法，包括顺序查找算法、折半查找算法、分块查找算法等。待讲到具体的查找算法时，会详细介绍这个公式的用法。