1. 查找章节引言（Chapter Introduction: Search）¶
组织与检索信息是大多数计算机 应用的核心，而查找无疑是所有 计算任务中最频繁执行的。 查找可以抽象地看作一个过程，用于确定 具有特定值的元素是否是特定集合的成员。 更常见的查找视角是尝试在 记录集合中找到具有 特定键值的记录，或者找出集合中键 值满足某一标准（例如落在某个 数值范围内）的那些记录。
我们可以如下正式定义查找。 假设我们有一个集合 L，包含 \(n\) 条记录，形式为
其中 \(I_j\) 是与键 \(k_j\) 相关联的信息， 来自第 \(j\) 条记录，\(1 \leq j \leq n\)。 给定特定的键值 \(K\)， 查找问题 是定位 L 中满足 \(k_j = K\) 的一条记录 \((k_j, I_j)\) （如果存在的话）。 查找 是一种系统的方法，用于 定位键值为 \(k_j = K\) 的记录。
成功查找 是找到键为 \(k_j = K\) 的记录的查找。 不成功查找 是 根本没有找到键为 \(k_j = K\) 的记录（且不存在这样的记录）。
精确匹配查询 是查找键值 与指定键值匹配的记录。 范围查询 是搜索所有键值 落在指定键值范围内的记录。
我们可以把查找算法归为三种通用的 方法：
顺序与链表方法。
按键值直接访问（散列）。
树索引方法。
这些方法中的任何一种都可能适合实现 字典 ADT。 然而，每种方法都有不同的性能特征，这使得它 在特定情况下成为首选方法。
本章考虑查找存储在 链表中的数据的各种方法。 这里的链表指任何链表实现，包括 链表或数组。 这些方法大多适用于序列 （即允许重复键值），尽管也有一些特殊 技术适用于 集合。 本章前三节的技术最 适合查找存储在 RAM 中的记录集合。 第 Hashing 章介绍散列，这是一种在 数组中组织数据的技术，使得数组中每条记录的位置 是其键值的函数。 散列适用于记录存储在 RAM 或 磁盘上的情况。
第 Indexing 章讨论在磁盘上组织 信息的基于树的方法，包括一种常用的文件结构， 称为 B 树。 几乎所有必须组织存储在磁盘上的大型记录集合的 程序，都使用散列或 B 树的某种变体。 散列只对某些访问应用（ 精确匹配查询）实用，并且通常只适用于不允许重复 键值的情况。 对于任何散列不合适的动态磁盘存储应用， B 树是首选方法。
