14 基本查找算法概述

在之前的文章中已经数据结构的基本知识，包括线性表、哈希表、树、图结构，并讨论了这些结构的存储映像，以及定义在其上的相应运算，并且我们概述了几种排序算法。除了基本排序算法外，我们接下来了解几种基于基本数据结构的查找算法，包括基于线性表的查找、基于树的查找、基于哈希的查找等。

在同样的数据结构中，我们通过前面介绍的线性结构、树和图保存数据以后，在使用时也需要通过查找来调用这个数据。由此可见，查找是数据结构算法中必须学习的内容之一。 在学习查找之前，需要先理解如下几个概念：

（1）列表：是由同一类型的数据元素或记录构成的集合，可以使用任意数据结构实现。 （2）关键字：是数据元素的某个数据项的值，能够标识列表中的一个或一组数据元素。如果一个关键字能够唯一标识列表中的一个数据元素，则称其为主关键字，否则称为次关键字。当数据元素中仅有一个数据项时，数据元素的值就是关键字。 （3）查找：根据指定的关键字的值，在某个列表中查找与关键字值相同的数据元素，并返回该数据元素在列表中的位置。如果找到相应的数据元素，则查找是成功的，否则查找就是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。显然，查找算法中涉及了如下3类参量。

①查找对象K，即具体找什么。 ②查找范围L，即在什么地方找。 ③K在L中的位置，即查找的结果是什么。

其中①、②是输入参量，③是输出参量。在函数中不能没有输入参量，可以使用函数返回值来表示输出参量。

（4）平均查找长度：为确定数据元素在列表中的位置，需要将关键字个数的期望值和指定值进行比较，这个期望值被称为查找算法在查找成功时的平均查找长度。如果列表的长度为n，查找成功时的平均查找长度为：

上述格式中各个参数的具体说明如下所示：

Pi ：表示查找列表中第i个数据元素的概率。 Ci ：当找到列表中第i个数据元素时，已经进行过的关键字比较次数。因为查找算法的基本运算是在关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。 有两大类查找的基本方法，分别是比较式查找法和计算式查找法。其中，比较式查找法又可以分为基于线性表的查找法和基于树的查找法，通常将计算式查找法称为哈希（Hash）查找法。

从数据结构方面看，多数查找算法是基于线性表的查找，而基于线性表的查找也可以用多种思想实现， 如暴力枚举思想的顺序查找算法，也有分治思想的分块查找算法，当然也有递归和迭代思想组合实现的折半查找算法，插值查找算法、还有斐波那契查找算法。

而基于二叉树数据结构的还有树表查找算法，我们在讲二叉树数据结构时已经了解并实现了，具体可以查看树的节点查找。此外还有基于哈希表的哈希查找算法，我们在讲数据结构哈希表时已经了解并实现了，具体可以查看哈希关键字的查找。在讲解图数据结构时，我们也顺带实现了深度优先搜索法和广度优先搜索法。以上这些查找方法都是基于数据结构，这里就不再赘述。