13.1. 章节引言：查找¶
信息的组织与检索是大多数计算机应用的核心，而查找无疑是所有计算任务中执行最频繁的。抽象地看，查找是一个判断具有特定值的元素是否属于某个特定集合的过程。更常见的看法则是：在记录集合中找出具有特定键值的那条记录，或者找出集合中键值满足某种条件（例如落在某个取值范围内）的那些记录。
下面给出查找的形式化定义。设有包含 \(n\) 条记录的集合 L，其形式为
其中 \(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 中的记录集合。 哈希 章介绍哈希——一种把数据组织到数组中、 使每条记录在数组中的位置由其键值决定的技术。 当记录存储在 RAM 或磁盘上时，都可以使用哈希。
索引 章讨论在磁盘上组织信息的基于树的方法，其中包括一种常用的文件结构——B 树。几乎所有需要组织存储在磁盘上的大型记录集合的程序，都会使用哈希或 B 树的某种变体。哈希只对某些访问方式（精确匹配查询）实用，而且通常只适用于不允许重复键值的情形。凡是不适合使用哈希的动态磁盘应用， B 树都是首选方法。
