查找：静态查找表的几种查找方法:顺序查找、折半查找、分块查找

对查找表的常见操作

1. 查找符合条件的数据元素
2. 插入、删除某个数据元素

静态查找表——只需进行1操作（仅关注查找速度即可）

动态查找表——也要进行2操作（除了查找速度，也要关注插/删操作是否方便实现）

查找算法的评价指标

查找⻓度——在查找运算中，需要对比关键字的次数称为查找⻓度
平均查找⻓度(ASL, Average Search Length)—— 所有查找过程中进行关键字的比较次数的平均值 

二、顺序查找

顺序查找，又叫“线性查找”，适用于顺序表、链表，表中元素有序无序都ok

算法思想

算法思想:从头到 jio 挨个找(或者反过来也OK)

 优化

• 若表中元素有序    

1. 当前关键字大于（或小于）目标关键字时，查找失败
2. 优点：查找失败时ASL更少
3. 查找判定树

         成功结点的关键字对比次数=结点所在层数

         失败结点的关键字对比次数=其父结点所在层数

• 若各个关键字被查概率不同    

1. 可按被查概率降序排列
2. 优点：查找成功时ASL更少

时间复杂度

O(n)

二、折半查找

折半查找，又称“二分查找”，仅适用于有序的顺序表。

算法思想

首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置：若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

折半查找判定树

构造

1. 如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
2. 如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素
3. 折半查找的判定树中mid=[(low+high)/2]，若 ，则对于任何⼀个结点，必有： 右⼦树结点数-左⼦树结点数=0或1

特性

折半查找的判定树⼀定是平衡⼆叉排序树（左<中<右）

折半查找的判定树中，只有最下⾯⼀层是不满的 

若查找表有n个关键字，则失败节点有n+1个

元素个数为n时树⾼h = ⌈log2(n + 1)⌉（不包含失败节点）

时间复杂度

折半查找的时间复杂度 = O(log2n)

三、分块查找

分块查找，又称“索引顺序查找”，数据分块存储，块内无序、块间有序

算法思想

索引表中记录每个分块最大关键字、分块的区间

先查索引表（顺序或折半）、再对分块内进行顺序查找

ASL

易错点

 对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low> high,要在low所指分块中查找