程序员学数据结构

第13章　查找：找你所需

对数据集进行排序的代价有时会比较高，但这种代价常常是一次性的，一旦建立起了已排序的数据集，程序在运行周期内的性能可以得到极大的提高。由于目标数据集是有序的，因此甚至还会提高向该数据集中添加对象操作的性能。

当需要在数据集中查找特定的元素或数值时，排序操作带来的性能提升才会真正地显现出来。本章我们将学习如何在数据集中进行查找操作，并了解在已排序的数据集中使用不同的查找算法会带来多大的性能收益。这里不会涉及所有可用的查找算法，仅对以下这3种最常用的查找算法进行讨论：

• 线性查找（linear search），又名顺序查找（sequential search）；
• 二分查找（binary search）；
• 跳跃查找（jump search）。

13.1　线性查找

线性查找也被称为顺序查找，它简单地循环访问数据集中的元素，通过某种比较函数来定位数据集中与条件相匹配的元素或数值。大多数线性查找算法都会返回一个数值，该数值用于表示匹配出的对象在数据集中的位置。当未找到匹配对象时，该数值可为某个不为数据集索引的值，如-1。另一种方案是直接返回匹配出的对象，若未找到匹配的对象，会返回null。

这是最简单的一种查找模式，其复杂度为O(n)。无论被查找的数据集有序与否，它的复杂度都不变。对于规模很小的数据集而言，这种查找方式不会带来任何问题，也被许多开发人员用在日常编程之中。然而，当数据集的规模很大时，使用别的查找方法会比顺序查找的效果更好。尤其是当被查找的数据集是由非常复杂的对象构成时，线性查找方法对该数据集的查找和分析操作会变得异常艰难。

本章中的每个代码示例都会对相应算法进行展现，其中会包含一些该算法所必需的方法，而这些方法的父类并不会出现在示例当中。此外，每个示例中查找的目标数据集将会在类层面进行定义，而这些代码也不会出现在示例当中。同样地，其他对象的实例化过程和这些数据集的赋值过程也不会出现在示例代码中。读者可在随书附带的资料中查阅完整的示例代码。 ...