一、查找

1、查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成 关键字：是数据元素中某个数据项的值，又称之为键值，可以标识一个数据元素

• 主关键字： 可以唯一地标识一个记录（比如身份证号码）
• 次关键字： 可以识别多个数据元素的关键字（比如微信昵称）

静态查找表：只作查找操作的查找表，它的主要操作有：

• 查找某个特定的数据元素是否在查找表中
• 检索某个特定的数据元素和各种属性

动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素

• 查找时插入数据元素
• 查找时删除数据元素

2、查找算法的评价指标

查找长度：在查找过程中，需要对比关键字的次数称为查找长度 平均查找长度（ASL, Average Search Length ）：所有查找过程中进行关键字的比较次数的平均值 ASL 的数量级反应了查找算法的时间复杂度 评价一个查找算法的效率时，通常考虑查找成功、查找失败两种情况的 ASL

二、静态查找表

1、顺序查找

又叫做线性查找 从表中第一个或最后一个记录开始，逐个进行比较。若某个记录的关键字和给定值相等则查找成功；如果查找到最后一个元素时，关键字和给定值还是不相等，则表示查找不成功

（1）性能分析

（3）顺序查找优化

• 针对有序表： 当被查找元素的值大于（或小于）查找表中间元素的值时，判定为失败

  

• 针对被查概率不相等

  

2、折半查找（二分查找）

查找步骤：

• 若给定值与中间记录的关键字相等，则查找成功
• 若给定值小于与中间记录的关键字，则在中间记录左半区继续查找
• 若给定值大于与中间记录的关键字，则在中间记录右半区继续查找 不断重复上述过程，直至成功；或无此记录，查找失败

（1）效率分析

（2）判定树的构造

• 如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素
• 如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
• 折半查找的判定树中, 则对于任何一个结点，必有：右树结点数-左子树结点数=0 或 1
• 折半查找的判定树一定是平衡二叉树
• 折半查找的判定树中，只有最下面一层是不满的；因此，元素个数为 n 时树高
• 判定树结点关键字：左<中<右，满足二叉排序树的定义
• 失败结点：n+1 个（等于成功结点的空链域数量）
• 折半查找的时间复杂度 =

3、分块查找（索引顺序表）

对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项

特点 ：块内无序，块间有序

查找时分两步进行

• 首先在索引表中查找待查找关键字所在的块。由于索引表是块间有序的，因此很容易利用其它查找算法（如二分查找）得到结果
• 接着在对应的块中查找目标值，由于块中大部分情况下是无序的，所以只能采用顺序查找

（1）效率分析

三、动态查找表

1、二叉排序树

• 若其左子树不空，则左子树上所有结点的值均小于根结点的值
• 若其右子树不空，则右子树上所有结点的值均大于根结点的值
• 其左、右子树也分别是二叉排序树

四、B 树和 B+树

1、B 树

是一种平衡的多路查找树，结点最大的孩子数目称之为 B 树的阶 (order)。和二叉排序树一样，每个结点把查找范围分为了两个区间，小于它的在左侧，大于它的在右侧 （尽可能满、尽可能平衡）