首页 > 试题广场 >

设有序表中有1000个元素，则用二分查找元素X最多需要比较(

[填空题]
设有序表中有1000个元素，则用二分查找元素X最多需要比较1次可知道所查找元素查找序列中。
添加回答
推荐
牛客-007头像 牛客-007
答案：10
二分查找的时间复杂度为logN
这里的比较次数为logN取上界，这里的对数是以2为底的
log1024=10,log512=9
所以这里log1000约等于9点几的小数，取上界为10
编辑于 2015-01-17 11:11:15 回复(0)
阿良头像 阿良
答案应该是9 假设查找元素在序列中，最后一次就可以不比较了，比如3个数，比较一次结果就出来了～
发表于 2015-09-07 08:06:05 回复(5)
Pis头像 Pis
确实是9啊，如果知道一定存在是9，如果知道一定不存在是10.
发表于 2016-03-15 21:26:54 回复(1)
wanlanwalan头像 wanlanwalan
比较10次。
1个元素的时候比较1次
2~3个元素比较2次
4~7个元素比较3次
8~15                4
16~31              5
32~63              6
64~127            7
128~255          8
256~511          9
512~1023       10
就是log2n取整后 +1
编辑于 2017-04-26 16:59:17 回复(0)
小小丽头像 小小丽
总结一下各位大佬的答案：

首先要弄清楚二分次数和比较次数。 比较次数＝二分次数＋1.

1000用二分法分到只剩一个数的次数是9次，如果问题是：
1000个数用二分法分到剩一个数，答案是9次，
是这里并没有比较最后剩下的那个数，所以总的比较次数为10。
 若已知一定存在此数，则最后一次不用比较了，总的为9次。 
就是大家所说的：比较次数为logN向上取整，二分次数为:logN 向下取整 log1000为9.XX，

综上所述所以比较次数为10，二分次数为9
发表于 2020-06-07 09:40:35 回复(0)
youyou.L头像 youyou.L
看了一下答案，很多都不完整。首先要弄清楚分的次数和比较次数是不一样的。 比较次数＝分的次数＋1. 1000用二分法分到只剩一个数的次数是9次，这里不比较，每次只对2去整。(如果问题是问1000个数用二分法分到剩一个数那么答案是9) 若我们是基于比较来得到最后剩下的一个数，这里是当只有一个数就停止操作。我们可以发现这个是和上面的一样，是9次。但是这里并没有比较最后剩下的那个数，所以总的比较次数为10。 若已知一定存在此数，则最后一次不用比较了，总的为9次。 总结出的公式:比较次数为logN向上取整 分的次数为:logN 向下取整 log1000为9.几，所以比较次数为10，二分次数为9
发表于 2017-09-29 13:58:28 回复(0)
热爱生活的僧人想活生生毕业头像 热爱生活的僧人想活生生毕业
发表于 2023-08-14 15:26:00 回复(0)
细雨湿身头像 细雨湿身
二分查找的时间复杂度为logN这里的比较次数为logN取上界
发表于 2016-10-11 16:05:20 回复(0)
scauweng头像 scauweng
我还是觉得是9 呀，，比如7,第一次范围变成3,第二次变为1, 1就不用判断了，直接是了不是吗，都假设了查找数一定存在。
发表于 2016-09-27 12:20:48 回复(0)
helloworld000000007头像 helloworld000000007
无论查找的元素是否存在，比较次数等于树的高度
编辑于 2016-08-14 17:06:55 回复(0)
尐短腿头像 尐短腿
下面说9次的  都把计算机想的太智能了！！  按你们这么说  知道一定不存在 也是9次！！ 、、 不要把他想的跟人一样具有推理能力！！ 觉得剩最后一个元素肯定是他没必要比较了么、、？ 计算机还是遵循   实践才是检验真理的唯一标准的！！！
发表于 2016-06-13 11:08:32 回复(0)
雪未成型头像 雪未成型
logn取下限再加1
发表于 2016-05-24 09:42:24 回复(0)
龙鱼颜（javaLong）头像 龙鱼颜（javaLong）
实际上我是查出来的，不过2的10次方1024所有十次吧
发表于 2015-10-23 20:39:38 回复(0)
MyGoodHelper头像 MyGoodHelper
10
最多比较次数，取logN取上界，大于等于log1000的最接近整数10
发表于 2015-01-17 18:05:36 回复(0)
大爱冷色调头像 大爱冷色调
11，logN取上界，log1000取上界为11
发表于 2015-01-12 21:56:06 回复(0)
提交观点

问题信息

排序
来自：4399游戏2015校...
上传者：小牧魔法袋
难度：
15条回答 18159浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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