3.2　查找算法简介

在复杂的数据结构中高效地查找数据是其非常重要的功能之一。最简单的方法是在每个数据点中查找所需数据，效率并不高。因此随着数据规模的增加，我们需要设计更复杂的算法来查找数据。

本节介绍以下查找算法：

• 线性查找（Linear Search）
• 二分查找（Binary Search）
• 插值查找（Interpolation Search）

我们详细了解一下它们各自的情况。

3.2.1　线性查找

查找数据的最简单策略就是线性查找，它简单地遍历每个元素以寻找目标，访问每个数据点从而查找匹配项，找到匹配项后，返回结果，算法退出循环，否则，算法将继续查找，直到到达数据末尾。线性查找的明显缺点是，由于固有的穷举搜索，它非常慢。它的优点是无须像本章介绍的其他算法那样，需要数据排好序。

我们看一下线性查找的代码：

现在，看一下代码的输出（见图3-15）。

需要注意的是，如果能成功找到数据，运行LinearSearch函数会返回True。

线性查找的性能

如上所述，线性查找是一种执行穷举搜索的简单算法，其最坏时间复杂度是O(N)。

3.2.2　二分查找

二分查找算法的前提条件是数据有序。算法反复地将当前列表分成两部分，跟踪最低和最高的两个索引，直到找到它要找的值为止：

输出结果如图3-16所示。

请注意，如果在输入列表中找到了值，调用BinarySearch函数将返回True。

二分查找的性能

二分查找之所以如此命名，是因为在每次迭代中，算法都会将数据分成两部分。如果数据有N项，则它最多需要O(log N)步来完成迭代，这意味着算法的运行时间为O(log N)。

3.2.3　插值查找

二分查找的基本逻辑是关注数据的中间部分。插值查找更加复杂，它使用目标值来估计元素在有序数组中的大概位置。让我们试着用一个例子来理解它：假设我们想在一本英文词典中搜索一个单词，比如单词river，我们将利用这些信息进行插值，并开始查找以字母r开头的单词，而不是翻到字典的中间开始查找。一个更通用的插值查找程序如下所示：

输出结果如图3-17所示。

请注意，在使用IntPolsearch函数之前，首先需要使用排序算法对数组进行排序。

插值查找的性能

如果数据分布不均匀，则插值查找算法的性能会很差，该算法的最坏时间复杂度是O(N)。如果数据分布得相当均匀，则最佳时间复杂度是O(log(log N))。