考纲内容
1.查找的基本概念
查找：从数据集合中查找满足某种条件的数据元素
查找结果中要注意，有查找成功和查找失败
查找表：用于查找的数据集合，定义有各种相关的操作：查询特定元素、根据条件检索数据、插入和删除。
静态/动态查找表：根据查找表中定义的操作种类区分
没有定义插入和删除的查找表称为静态查找表（相当于只读，不可更改）
允许插入和删除的查找表则称为动态查找表
根据这个区别，两种查找表分别适合不同种类的查找方法：静态表比较适合顺序/折半/散列查找，动态表适合二叉排序树查找和散列查找。
关键字：数据元素中用于唯一地确定某个数据项的值。
平均查找长度：查找长度指的是一次查找需要比较的关键字的次数。平均查找长度为所有查找过程中进行关键字的比较次数的平均值。
平均查找长度的计算公式：
2.线性的查找结构
有顺序查找、折半查找和分块查找这三种
*这里注意，这些查找方法对于顺序表和链表都是适合的，这两种结构都属于线性表
(1)顺序查找
也称线性查找 对于一般的线性表（这里指的是没有排过序的，也就是大多数情况下的线性表） 顺序查找其实就是最简单的暴力查找算法 从头到尾，逐个根据查找条件对每个关键字进行比较，查找到线性表尾部才能得出查找结果（成功或失败） 一般顺序查找的伪代码
*关于这里的“哨兵”：
链表中使用的，为了统一操作的附加头结点也是这种哨兵机制的一种。
顺序查找的算法复杂度分析：（通过平均查找长度长度进行分析）
当每个元素的查找概率相同时，查找成功的平均查找长度ASL是(n+1)/2，失败的ASL是n+1。
顺序查找的特殊情况：有序查找表的情况
有序查找表的算法复杂度只有在查找失败的情况下才有区别
有序表的情况中，当中途确定已经查找失败时，可以直接退出查找
在最坏情况下，到达结尾才发现查找失败，这时的平均查找长度和无序的情况相等。