具有12个关键字的有序表，折半查找的平均查找长度（）

[单选题]

```
3.1
```
```
4
```
```
2.5
```
```
5
```

查看正确选项

BugFree

从折半查找的过程看，以有序表的中间记录作为比较对象，并以中间记录将表分割为两个子表，对子表继续上述操作。所以，对表中每个记录的查找过程，可用二叉树来描述，二叉树中的每个结点对应有序表中的一个记录，结点中的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树。

长度为n的折半查找判定树的构造方法为：

⑴ 当n=0时，折半查找判定树为空；

⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

对于折半查找判定树，需要补充以下两点：

⑴ 折半查找判定树是一棵二叉排序树，即每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值；

⑵ 折半查找判定树中的结点都是查找成功的情况，将每个结点的空指针指向一个实际上并不存在的结点——称为外结点，所有外结点即是查找不成功的情况。如果有序表的长度为n，则外结点一定有n+1个。在折半查找判定树中，某结点所在的层数即是查找该结点的比较次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。例如，长度为12的有序表的平均查找长度为：

ASL=（1*1+2*2+3*4+4*5）/12=37/12=3.0833

欢迎各位关注在下的微信公众号“张氏文画”，不光有新鲜的 LeetCode 题解，还有经典的文章及短视频和大家分享，一起嘿嘿嘿