1. 章节引言：查找¶

组织和检索信息是大多数计算机应用的核心， 而查找无疑是一切计算任务中最常执行的操作。 抽象地看，查找可以视为确定具有特定值的元素是否 是某个特定集合成员的过程。 更常见的查找观点是，试图 在记录集合中找到具有特定键值的记录， 或者找到集合中键值满足某种准则（例如落在某个 值范围内）的记录。

我们可以如下正式地定义查找。 假设我们有一个形式为下面的 \(n\) 条记录的集合 L

其中对 \(1 \leq j \leq n\)，\(I_j\) 是与记录 \(j\) 键 \(k_j\) 关联的信息。 给定一个特定的键值 \(K\)， 查找问题 是在 L 中定位记录 \((k_j, I_j)\)，使得 \(k_j = K\) （如果存在的话）。 查找 是一种系统化定位 键值 \(k_j = K\) 的记录（或记录）的方法。

成功查找 是找到键 \(k_j = K\) 的记录的查找。 不成功查找 是未找到键 \(k_j = K\) 的记录的查找（并且这样的记录不存在）。

精确匹配查询 是查找键值与 指定键值匹配的记录的查找。 范围查询 是搜索所有键值落在 指定键值范围内的记录的查找。

我们可以把查找算法归纳为三种 一般方法：

1. 顺序与线性表方法。

2. 按键值直接访问（散列）。

3. 树索引方法。

这些方法中的任何一种都可能适合实现 字典 ADT。 但是，每种方法都有不同的性能特征，使其 在特定情况下成为首选方法。

本章考虑查找存储在线性表中的数据的方法。 这里的线性表指任何线性表实现，包括 链表或数组。 这些方法大多适用于序列 （也就是说，允许重复键值），尽管也有一些 集合 适用的特殊技巧。 这些技巧最适合查找存储在 RAM 中的记录集合。 散列 是一种在数组中组织数据 的技巧，使得每条记录在数组内的位置都是其键值的 函数。 散列适用于存储在 RAM 中或磁盘上的记录。