【算法/数据结构】查找1_线性表的查找
查找表： 一组记录组成的表，每个记录可能有多个数据项，因此使用某个关键字来代表该记录 可理解为如下示例
map<string,pair<int,int>> mp
mp中，mp["abc"]为关键字为"abc"的记录，数据项是一个pair<int,int>
对某数据项的寻找，即使用该数据项对应记录的关键字对记录进行寻找
平均查找长度（ASL）： 查找的主要时间花在比较上，引入ASL作为统计平均查找比较次数的参考。
定义： 对于 $n$ 个记录，$p_{i}$为查找第 $i$ 个记录的概率， $c_{i}$ 为查找第 $i$ 个记录所需要的比较次数，则有 $ASL = \sum_{i=1}^{n} p_{i}c_{n} $
一般认为 $p_{i} = \frac{1}{n}$ 即 每个记录都均等概率被找到
ASL 分为 $ASL_{成功}$和 $ASL_{失败}$
$ASL_{成功}$：
对于所有在查找表内的记录，计算其平均比较次数，如下图例
$ASL_{失败}$：
对于任意不在查找表内的记录对应的关键字$k$，计算从查找表内查找直到发现该记录不在表内的比较次数的平均
线性表的查找
- 顺序查找 原理 从查找表的表头扫到表尾，比较待找关键字与表中关键字
平均查找长度 对每个表中关键字查找，一共比较 $1+2+...+(n)$次 $ASL_{成功} = \frac{ \frac{n(n-1)}{2}}{n} = \frac{n-1}{2}$
对每个非表中的关键字，都得从头扫到尾 因此每个非表中关键字 比较次数都是 $n$ $ASL_{失败} = n$
- 折半查找 原理 对于关键字排列有序的查找表来说，查找某个关键字$k$只需要进行二分查找的思想，即每次迭代都判断当前指针指向的关键字与$k$的大小，满足某种偏序关系，使区间不断缩小，直到结束
二分判定树
将查找过程化为树，即当前mid为根节点，$[left,mid)$为左子树 $[mid,right]$为右子树，此树满足某种有序性
内部结点是所有关键字的集合 $[0,1,2,3,4,5,6,7,8,9,10]$ 有 $n$ 个
而外部节点是不在该查找表内的关键字 即 $[<0,0-1,1-2,...,>10]$ 有 $n+1$ 个
查找次数 从二分判定树中我们可以发现，当查找的关键字在查找表中时，查找的比较次数为该关键字在二分判定树中的层数，要查找的关键字不在查找表中时，即查找失败的比较次数为失败区间所在结点的层数。 $ASL_{成功} = \frac{1+22+34+4*4}{11}$
$ASL_{失败} = \frac{44+58}{12}$
3. 分块查找
分块查找是应用于数据表加索引表结合的结构的算法
索引表中每一个索引项包含 关键字 和 该索引项指向的数据表的地址
数据表的每一个数据项也包含关键字 用于顺序查找数据项
分块查找的索引表需要有序，这样才能确定数据表所包含的数据项的关键字的范围，即对索引表相邻两索引项的关键字k1 k2 其之间的数据项的关键字必须处于 k1 k2 之间 这样才有办法分块查找找到
而索引表找到了之后的数据表表内可以无序，对数据表表内项进行顺序查找
性能比较 分块查找性能介于顺序查找和二分查找之间