作者：稀饭
本文约字，数理内容较少，泛读需6分钟，精读需12分钟。1、查找的基本概念
（1）简介：查找又称检索，是计算机进行数据处理时极为常用的操作之一。查找在日常生活中几乎无处不在，其特点是在一个数据集中找到一个符合条件的元素，若查找成功，则返回该元素，否则提示查找失败。
（2）相关术语
[1]查找表：由一组数据元素组成（或记录）构成的集合。
[2]关键字：查找表中的某个数据项。
[3]主关键字：取值唯一的关键字。
[4]次关键字：取值不唯一的关键字。
[5]查找：根据给定的关键字的值，在查找表中找到一个关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置的过程。
[6]查找成功：在执行查找操作时，若找到指定数据元素，则称查找成功。
[7]查找失败：在执行查找操作时，若找不到指定数据元素，则称查找失败，此时返回空。
[8]静态查找：在查找过程中，只是对数据元素执行查找操作，而不对其执行其他操作。
[9]动态查找：在查找过程中，不仅对数据元素执行查找操作，同时有其他操作（如插入）。
[10]静态查找表：只执行静态查找的查找表。
[11]动态查找表：执行动态查找的查找表。
[12]内查找：在执行查找操作时，查找表中的所有数据元素都存在内存中。
[13]外查找：由于查找表中的数据元素太多，不能同时放在内存中，而需要将一部分数据元素放在外存中，从而导致在执行查找操作时需要访问外存。
[14]查找长度：在查找运算中，给定值与关键字的比较次数称为查找长度。
[15]平均查找长度（ASL）：查找长度的期望值被称为平均查找长度。对于含有n个数据元素的查找表，查找成功时的平均查找长度为。其中，为在表中查找第i个数据元素的概率，满足；是指找到关键字与给定值相等的第i个记录时，给定值与表中关键字的比较次数。
（3）查找表的基本操作类型
[1]类型一：查找指定的元素是否在查找表内；
[2]类型二：检索指定的数据元素；
[3]类型三：在查找表中插入指定元素；
[4]类型四：在查找表中删除指定元素。
（4）查找表的抽象数据类型
[1]数据对象：具有相同特性的数据元素集合。每个数据元素均含有类型相同、可唯一标识的数据元素的关键字。
[2]数据关系：数据元素同属于一个集合。
2、基于静态查找表的查找
（1）静态查找表的抽象数据类型
[1]数据对象：具有相同特性的数据元素集合。每个数据元素均含有类型相同、可唯一标识数据元素的关键字。
[2]数据关系：数据元素同属于一个集合。
（2）顺序查找：又称作线性查找。它是将给定值与静态查找表中数据元素的关键字逐个比较，若表中某个元素的关键字和给定值相等，则说明查找成功，找到所查的数据元素；若直到表中数据元素的关键字全部比较完毕，仍未找到与给定值相等的关键字，则说明查找失败，即表中无所查的数据元素。
（3）折半查找：又称二分法查找。其首先是在静态查找表中确定待查找的范围（查找区间），然后从该范围的中间位置开始，若给定值与该位置的关键字相等，则查找成功；若给定值大于该位置的关键字，则在该范围的右半部分继续查找，否则在该范围的左半部分继续查找。通过不断重复该过程，直到查找成功，或者查找范围为空时结束查找（此时查找失败）。
（4）索引查找：又称分块查找，其通过将静态查找表分成若干块（子表），然后对各个子表建立一个索引项，并将其存储在索引表中。在执行查找时，先确定数据元素所在的子表，然后在该子表中顺序查找该数据元素。
3、基于动态查找表的查找
（1）动态查找表的抽象数据类型
[1]数据对象：具有相同特性的数据元素集合。每个数据元素均含有类型相同、可唯一标识数据元素的关键字。
[2]数据关系：数据元素同属于一个集合。
（2）树查找
[1]基于二叉排序树：二叉排序树又称二叉查找树，它要么是空树，要么需要满足三个性质，一是“若根结点的左子树非空，则左子树中所有结点的值都小于根结点的值”；二是“若根结点的右子树非空，则右子树中所有结点的值都大于根结点的值”；三是“根结点的左、右子树均是一棵二叉排序树”。根据BST的性质可知，中序遍历一棵二叉排序树可以得到一个递增序列。
[2]基于平衡二叉树：平衡二叉树又称AVL树，是指创建过程中需要调整树的形态，以保证树的深度尽可能地小并且满足BST的性质。平衡二叉树要么是空树，要么是满足某一性质的二叉排序树，即每个结点的左子树和右子树的深度之差的绝对值不超过1，且每个结点的左子树和右子树均是一颗平衡二叉树。
[3]基于B-树：当查找表中数据元素太多以至于无法一次性读入内存时，可以采用B-树来进行查找。B-树是一种平衡多叉树。一颗m阶B-树要么是空树，要么满足几个性质，一是“树中每个结点最多含有m棵子树”；二是“若根结点不是叶子节点，则至少含有两棵子树”；三是“除根结点外所有非叶子结点至少有[m/2]棵子树”；四是“所有外部结点都出现在同一层，并且不带信息”；五是“所有非叶子结点的结构如下表所示”。
[4]基于B+树：B+树是B-树的一种变形树，但比B-树更适合于操作系统的文件索引和数据库索引。B+树要么是空树，要么满足几个性质，一是“每个非叶子结点最多含有m棵子树”；二是“根结点要么没有子树，要么最小有两棵子树”；三是“除了根结点外，每个结点至少含有[m/2]棵子树”；四是“任一结点中若含有n个关键字，则该结点含有n棵子树”；五是“叶子结点中包含了指向该结点的指针，并且结点按照关键字从小到大依次链接，所有叶子结点的关键字集合包含全部的关键字”；六是“所有非叶子节点仅含有所有孩子结点的最大关键字和指向该孩子结点的指针。
广告区↓
重磅资料上新——《互联网数据分析岗位校招备战手册》
稀饭的写作小屋