首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
在154个元素组成有序表进行二分法查找,可能的比较次数为
[不定项选择题]
在154个元素组成有序表进行二分法查找,可能的比较次数为?
10
8
4
1
查看答案及解析
添加笔记
求解答(10)
邀请回答
收藏(812)
分享
19个回答
添加回答
100
奋斗吧少年
折半查找过程可用二叉树来描述,把有序表中间位置上的结点作为树的根结点,左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径,比较的次数就是该路径中结点的个数,即,该结点在树中的层数。 所以该题可以转换为求有154个结点的二叉树有几层,小于等于这个层数的数值就是答案。 又知,深度为K的二叉树最多有2的K次方-1个结点,深度为7的二叉树最多有127个结点,深度为8的二叉树最多有255个结点,所以154个结点的二叉树有8层。
发表于 2016-04-02 16:26:46
回复(7)
32
牛客749711号
[log2(154)] = 7,最差的情况下找8次,所以8次及8次以内都有可能找到。
发表于 2016-03-24 10:18:47
回复(5)
10
runner
为什么是按2的次方来算?二分法不是会每次减一吗。。这样的话2的n方就不准确了啊!我在纸上推算和代码测试了最多都只有7次。。 求解答
发表于 2016-03-24 12:08:03
回复(9)
3
白起丶
用二分查找法
查找某个数据,最多需要比较(logn)+1次,注意
这里的对数函数是以2为底,并且是向下取整
发表于 2020-07-10 11:51:58
回复(0)
3
java牛马
最开始我认为2
8=
256就没选B。原来是欠考虑了 。二分查找可以看做是对二叉树的查找,对于完全二叉树而言,一层树为一个结点,二层树为3个,三层为8-1 (2的三次方-1)。。。。七层2
7
-1= 127,剩下的还能组成一层结点,所以是8层
发表于 2017-07-13 21:45:36
回复(0)
2
传琦
通过判定树可以描述二分查找过程,查找成功的最大次数为:log
2
n(取下限),查找不成功的次数为
log
2
n(取下限)+1;
因此
154个元素组成有序表进行二分法查找,最多比较次数为查找不成功的的次数:
log
2
n(取下限)+1=8
编辑于 2016-07-20 11:44:15
回复(0)
1
wanlanwalan
过程可用二叉树来描述,把有序表中间位置上的结点作为树的根结点,左子表和右子表分别对应树的左子树和右子树。折半查找的过程就是走一条从根节点到被查结点的一条路径,比较的次数就是该路径中结点的个数,即,该结点在树中的层数。 所以该题可以转换为求有154个结点的二叉树有几层,小于等于这个层数的数值就是答案。 又知,深度为K的二叉树最多有2的K次方-1个结点,深度为7的二叉树最多有127个结点,深度为8的二叉树最多有255个结点,所以154个结点的二叉树有8层。
发表于 2017-04-26 15:22:04
回复(0)
0
牛客287369450号
2的7次方=128,解法应该是:
(log158)的向下取整=7,再加上1,为8
发表于 2023-02-22 19:45:00
回复(0)
0
周米粒
8次我知道 1次我也知道 那么为什么有4次?
发表于 2020-12-17 22:28:27
回复(0)
0
Daijinyao
这里可以假设我们要查找的元素为负无穷或者正无穷,那么这将是最坏的查找情况。我们需要查找的次数n应该有下面的关系:
2
(n-1)
<=154<=2
n
可以理解为我们需要遍历整个列表中的元素(因为最后要和第一个或者最后一个元素比较)
发表于 2020-07-01 16:32:12
回复(0)
0
你的offer对我打了烊
只要不大于最大查找次数都ojbk
发表于 2020-05-15 22:43:25
回复(0)
0
Fcq11
将其转换为一棵二叉树 对应的树的结点个数。然后其层数就是二分查找的比较次数
发表于 2020-03-14 17:17:41
回复(0)
0
ting9210120
[log154]=8,也就是说最差的情况下要查找8次。8次以内都有可能
发表于 2018-12-26 17:17:34
回复(0)
0
大将军豆腐脑好
自己只算了2的8次方,大于154,就把小于7的值都算进去了。
发表于 2017-05-07 15:07:47
回复(0)
0
牛客557720号
其实我觉得可以用除以2的办法,除几次能到0以下,那答案就是几
发表于 2016-09-12 17:14:24
回复(0)
0
huixieqingchun
折半查找,最坏的情况下只能有8次
发表于 2016-05-12 13:27:19
回复(0)
0
远方的范特西
可以用归纳法来证明,如果总共有n个元素,2
i
=<n<2
(i+1)
-1,则最多需要查找i次。
发表于 2016-04-01 10:46:08
回复(0)
0
HsLiu
用12345举例,二分查找5需要3次,就知道这题为什么也需要8次了
发表于 2016-03-30 00:22:09
回复(1)
0
ryl
154个元素,排成二叉树需要(2^8-1>154>2^7-1)8层,所以最多8次比较。
发表于 2016-03-28 20:35:37
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
查找
来自:
2016乐视暑期实习生...
难度:
19条回答
812收藏
14625浏览
热门推荐
相关试题
在mysql中,以下哪种方式可以开...
数据库
评论
(31)
来自
2016乐视暑期实习生招...
以下不同的数据库类型中,哪些不属于...
数据库
评论
(14)
来自
2016乐视暑期实习生招...
精俭排序,即一对数字不进行两次和两...
排序
评论
(21)
来自
2016乐视暑期实习生招...
字符串最后一个单词的长度
字符串
评论
(3633)
来自
2016乐视暑期实习生招...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题