#笔记整理

查找表 由同一类型的数据元素（记录）构成的集合。 查找的定义 给定一个值 key，在含有 n 个记录的表中找出关键字等于 key 的记录。若找到，则查找成功，返回该记录的信息或该记录在表中的位置；否则查找失败，返回相关的指示信息。

静态查找表(Static Search Table)——基于线性表的查找法 查询某个特定的元素是否在表中；检索某个特定的元素的各种属性。 即：只作查找操作的查找表。

动态查找表(Dynamic Search Table)——基于树表的查找法 若在查找的同时对表做修改运算(如插入和删除)。 即在查找过程中同时插入查找表中不存在的数据元素，或删除某个已存在的数据元素。

主关键字： 能唯一标识一个记录的关键字。 次关键字： 能标识多个记录的关键字。

平均查找长度 ASL(Average Search Length) ： 为确定数据元素在查找表中的位置， 需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

三种在线性表上进行查找的方法：

因为不考虑在查找的同时对表做修改，故上述三种查找操作都是在静态查找表上实现的。

又叫线性查找，是最基本的查找技术，它的查找过程是： 从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

折半查找的思想： 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

要求待查找的表必须是按关键字大小有序排列的顺序表。

判定树(比较树) 折半查找过程可用二叉树来描述，把当前查找区间的中间位置上的记录作为根，左子表和右子表的中间位置的记录分别作为根的左子树和右子树，这样形成的树称为折半查找判定树（比较树）。 折半查找效率分析 如果查找表中有 n 个元素，查找成功和失败的平均查找长度与有 n 个结点的完全二叉树的高度相同。即： 示例：

插值查找法是根据要查找的关键字 Key 与查找表中最大最小记录的关键字比较后的查找方法。 前提： 关键字值分布比较均匀。 思路： 折半查找的 m i d mid mid = l o w + h i g h 2 {low + high} \over {2} 2