查找——平均查找长度

查找有以下查找方式：

顺序表查找
二分查找
索引表查找
二叉排序树查找
哈希表查找

接下来整理一下上面每个方式的平均查找长度

顺序表查找ASL

如果每个关键字查找概率相同，则ASL = (n+1)/2。
一般都是概率相同。

二分查找ASL

举例说明：

这是一个有序序列(下标和关键字相同)：
0   1   2   3   4  

初始化：low = 0, high = 4

第一次：
    mid = (0+4)/2 = 2 , 则2为第一次找到的关键字。
    所以n2 = 1

第二次：
    如果mid小了,则low = 3, mid = (3+4)/2=3;则3为第二次找到的关键字
    如果mid大了,则high = 1, mid = (0+1)/2=0;则0为第二次找到的关键字
    所以n0 = n3 = 2

第三次：
    过程不在赘述
    n1 = n4 = 3

所以ASL = (n0+n1+n2+n3+n4)/5 = 11/5

索引表ASL

假设序列分成了n块，每块k个元素，那么ASL = LB + LA
那么ASL = (1+n)/2 + (1+k)/2

二叉排序树

根据给定的序列建立好二叉排序树。
比如序列 20, 12, 42, 31, 18, 14, 28
二叉排序树如下：

              20
        12          42
          18      31
        14      28

假设有n个结点，则ASL = 这里写图片描述

这里的hi是每个结点的深度，比如20的深度为1, 12的深度为2等，所以上面例子的ASL = (1+2+2+3+3+4+4)/7 = 19/7。

哈希表ASL

1.线性探测法：

假设第i个关键字的探测次数为Pi

则ASL = 这里写图片描述

举例：
已知待散列的线性表为(36, 15, 40, 63, 22)，散列用的一维地址空间为[0..6]，假定选用的散列函数为H(k) = K mod 7，采用线性探测解决冲突
36 mod 7 = 1
15 mod 7 = 1
40 mod 7 = 5
63 mod 7 = 0
22 mod 7 = 1

所以36的探测次数为0，15的探测次数为1，40的探测次数为0，63的探测次数为0，22的探测次数为2
则ASL = ((0+1) + (1+1) + (0+1) + (0+1) + (2+1)) / 5 = 1.6

2.链地址法
还是上面的例子线性表为(36, 15, 40, 63, 22)，链地址给[0..6]

0 -> 63
1 -> 36 -> 15 -> 22
2 -> NULL
3 -> NULL
4 -> NULL
5 -> 40
6 -> NULL
第一列有3个关键字63,36,40; 第二列有1个关键字15; 第三列有1个关键字22

∴ ASL = (1 * 3 + 2 + 3) / 5 = 1.6

秒客网