我要招人

去企业版

首页 > 试题广场 >

有个长度为12的无重复有序表，按折半查找法进行查找，在表内各

[单选题]

有个长度为12的无重复有序表，按折半查找法进行查找，在表内各元素等概率情况下，查找成功所需的平均比较（三元比较）的次数为（）

```
35/12
```
```
37/12
```
```
39/12
```
```
43/12
```

查看答案及解析

前程似锦的垂耳兔很喜欢吃火锅

由题目已知元素序号(即下标)范围为1～12。查找1次成功的结点为：6。查找2次成功的结点为：3，9。查找3次成功的结点为：1，4，7，11。查找4次成功的结点为：2，5，8，10，12。成功查找所有结点的总的比较次数为:1×1+2×2+3×4+4×5=37平均比较次数为37／12。因此选择B。

发表于 2019-04-18 15:15:16 回复(5)

LauZyHou

一共12张牌。1费1张，2费2张，3费4张，4费5张(4费最多可以8张)。然后计算总费用就行了，37费。

发表于 2020-05-16 09:57:45 回复(7)

来一个西安的offer

发表于 2020-07-03 14:26:15 回复(0)

牛客4938kunn

构建了从1——12的搜索树，请指正图片说明

发表于 2021-07-22 09:31:54 回复(0)

校草王风风的室友

二分查找的次数相同的数字的个数是1，2，4，8，18等2的幂，12个数字的查找1，2，3，4次的个数为1，2，4，5的比较次数为:1×1+2×2+3×4+4×5=37，平均次数为37/12.

发表于 2019-11-19 22:13:06 回复(0)

虚拟小菜鸟

总共12个数，最多查找次数为4次。查找一次找到的数为1个(两点(两个初始端点)则有一个中点(之后总共有3个点))；查找2次能找到的为2个(翻倍，3点之间有2个中点(这时总共5个点))；查找3次能找到的有4个(翻倍，5个点有4个中点(这时总共为9个点))；查找4次的按之前的规律应该能找到8个(翻倍)，但是总共只有12个数，前面找到了7个了，因此查找4次能找到剩下的5个值。总结:(1个1次，2个2次，4个3次，5个4次)共37次。

发表于 2021-11-09 12:57:23 回复(0)

凤铃

最后一次查找成功到的数据个数根据数据个数不同有不同。

发表于 2022-01-04 16:40:49 回复(0)

NightCrow2023

缘来如此，

发表于 2021-12-18 10:58:49 回复(0)

米奇伤心屋

等概率下，折半查找的平均查找长度公式为：ASL={[(n+1)/n]*log2^(n+1)}-1

发表于 2021-08-12 12:56:01 回复(0)

提交观点

问题信息

查找

来自：小米2019秋招测试开...

上传者：小小

难度：

9条回答 694收藏 9098浏览

有个长度为12的无重复有序表，按折半查找法进行查找，在表内各

问题信息

热门推荐

相关试题