首页 > 试题广场 >

12个元素的排序数组进行二分查找，每个元素被查找的概率是相等

[填空题]
12个元素的排序数组进行二分查找，每个元素被查找的概率是相等的，平均比较次数为1。（分数作答）
查看正确选项
添加回答
推荐
Trenson头像 Trenson 
平均查找长度公式为：ASL={[(n+1)/n]*log2^(n+1)}-1，也可以直接算出来，1*1+2*2+3*4+4*5=37，故其次数为37/12。
编辑于 2014-12-09 17:09:25 回复(0)
更多回答
Da_Ben头像 Da_Ben
查找一次：1（恰好为数组中间的值）
查找两次：2（恰好为第二次二分的中间值）
查找三次：4（恰好为第三次二分的中间值）
查找四次：5（12-1-2-4=5，其余情况）

求期望：(1*1+2*2+3*4+4*5)/12
发表于 2015-09-03 10:11:52 回复(0)
已注销头像 已注销
二分查找其实就是二叉排序树，12个元素对应12个节点，每个元素的查找次数是从该节点到根节点的长度。所以这道题算法应该是： （1*1+2*2+3*4+4*5）/12
每一层的节点数  乘  层数之和  除  总节点数
根节点算作第一层。
发表于 2017-02-09 10:26:29 回复(0)
henghengbiang头像 henghengbiang
37/12不就是等于3吗？以为要填整数！！！
发表于 2015-05-29 15:28:03 回复(5)
福小博头像 福小博
画出判定树，第一层必为1个结点，第二层2个，第三层4个，剩余5个在第四层，所以(1*1+2*2+3*4+4*5)/12=37/12。
发表于 2016-06-30 10:40:17 回复(3)
被支配的恐惧头像 被支配的恐惧
二分查找其实就是二叉排序树，12个元素对应12个节点，每个元素的查找次数是从该节点到根节点的长度。所以这道题算法应该是： （1*1+2*2+3*4+4*5）/12 ==  （）层数*节点数）/12
每一层的节点数  乘  层数之和  除  总节点数
根节点算作第一层。
发表于 2017-04-15 11:07:49 回复(0)
kingdom王者头像 kingdom王者
手贱转换成小数。。。。。
发表于 2017-03-29 23:37:59 回复(0)
向左向右向前看头像 向左向右向前看
天哪 我保留了3位小数
发表于 2016-05-15 21:28:04 回复(0)
叫我大头头像 叫我大头
麻麻地，又搞错了
发表于 2017-12-27 21:51:05 回复(0)
过往云烟123头像 过往云烟123
查找成功时的ASL。
发表于 2016-08-06 16:52:41 回复(0)
Deret头像 Deret
37/12
发表于 2016-03-09 22:34:51 回复(0)
codersong头像 codersong
哎，填了个3.1错了
发表于 2015-10-10 17:17:07 回复(0)
提交观点

问题信息

复杂度 人人网
来自：人人网2015研发笔试卷E
上传者：Leon
难度：
12条回答 18253浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号