第8章　查　找

本章介绍了查找的几种基本方法,并对各种算法的性能及时间、空间复杂度进行了分析。查找表（search table）是由同一类型的元素构成的数据集合,对数据元素间的关系未做限定。所谓查找即为在一个含有众多数据元素（或记录）的查找表中按照一定的要求找到特定的元素或记录。

查找表通常可以分为两类:静态查找和动态查找。静态查找表（static search table）仅作为查询和检索操作的查找表,不会改变表中的数据。常见的静态查找方式有顺序查找、折半查找、分块查找等。动态查找表（dynamic search table）除了对查找表进行查找操作外,还可能进行插入或删除表中数据元素的操作,即表中数据是动态变化的。动态查找方式包括树型查找、散列查找等。