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

[单选题]

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

查看正确选项

微201903010939141

原理和其他热评一样，至于比较次数的根据：因为我们求得是平均查找长度，所以我们要计算每一个元素的查找长度，如果这个数在第三层，那么我们就需要二分查找三次才能找到这个数，这也就是比较次数的来源。

如果第三层有三个元素，那么这三个元素，每个三个寻找都要查找比较三次，所有第三层数的比较次数也就是3*3次，然后再加上其他层数的比较次数，就是最后结果。

发表于 2019-03-13 11:30:05 回复(0)

牛客1512337号

发表于 2018-06-02 09:11:21 回复(7)

RenaissanceWhy

将12个数画成完全二叉树，第一层有1个、第二次2个、第三层4个，第四层只有5个。

二分查找时：

第一层需要比较1次

第二两个数，每个比较2次

第三层四个数，每个比较3次

第四层五个数，每个比较4次

则平均查找长度即为：（1+2*2+3*4+4*5）/12 = 37/12 = 3.0833 即为 A、3.1

发表于 2017-05-04 17:45:32 回复(8)

大将军豆腐脑好

二分查找平均时间复杂度log n，带入12得到了大概3点多，根据答案选择。

发表于 2017-07-23 09:09:37 回复(11)

坚持救是胜利

快速解题思路：

log2n=m =>2^m=n =>2^m=12 =>2³=8 小于12 小于 2⁴ 故，m介于3和4之间

发表于 2020-05-13 18:39:11 回复(0)

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 题解，还有经典的文章及短视频和大家分享，一起嘿嘿嘿