（二十）数据结构-查找的基本概念

一、查找的基本概念

1. 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
2. 查找表：用于查找的数据集合称为查找表，分为静态查找表（只需要查找操作）、动态查找表（除了查找，还需要增/删数据元素）
   1. 查询某个特定的数据元素是否在查找表中
   2. 检索满足条件的某个特定的数据元素的各种属性
   3. 在查找表中插入一个数据元素
   4. 从查找表中删除某个数据元素
3. 关键字(具有唯一性)：数据元素中唯一标识某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的
4. 平均查找长度（ASL）：在查找过程中，一次查找的长度上是指需要比较的关键字的次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值

二、顺序查找（线性查找）

对于顺序表和链表都是适用的

• 顺序查找通常分为对 一般的无序线性表的顺序查找和 对按关键字有序的关键字有序的线性表的顺序查找
  • 对于顺序表，可通过数组下标递增来顺序扫描每个元素
  • 对于链表，可以通过指针next来依次扫描每个元素

2.2一般线性表的顺序查找

思想：从线性表的一段开始，逐个检查关键字是否满足给定的条件

2.2.1查找效率分析

2.3有序表的顺序查找

若在查找之前，就已经知道了表的关键字是有序的，则查找失败就可以不用在比较到表的定义段就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度

2.4用查找判定树分析ASL

2.5被查找概率不同

2.6知识回顾与重要考点

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

仅适用于有序的顺序表

思想：首先将给定值key与表中中间位置的元素进行比较，若相等则查找成功，返回该元素的存储位置；
若不相等，则所需查找的元素只能在中间元素以外的前半部分或后半部分
（查找升序排序时，给定值key大于中间元素，则所查找到的元素只可能在后半部分）
最后在缩小的范围内进行进行同样的查找，如此重复…

折半查找的速度O(log2n)不一定比顺序查找(n)快

折半查找的判定树是平衡二叉树（结点），但并不意味任意的平衡二叉树（高度）符合折半查找的定义

四、分块查找（索引顺序查找）

吸收了顺序查找和折半查找的优先，既有动态结构，又适用于快速查找