首页 > 试题广场 >

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

[单选题]

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

  • 25
  • 10
  • 7
  • 1
查看正确选项
添加回答
大将军豆腐脑好头像 大将军豆腐脑好
二分查找的最坏时间复杂度为O(log n)，把n等于1000带入得到，log1000＞9，＜10，取整那么至少10
发表于 2017-07-23 09:02:47 回复(2)
大星星和小猩猩头像 大星星和小猩猩
如果有序表中有N个元素，那么二分查找查找元素X最多需要比较 log2(N+1)向上取整 次。
举个例子，假设有4个元素，1，2，3，4，那么假如我要查找4，先是查到2，然后查到3，接着是才是4，要查3次，注意不是2次哦。
log2（4+1）向上取整为3.
发表于 2020-04-08 00:49:40 回复(0)
微尘Ss头像 微尘Ss
log(1000)向上取整
发表于 2019-03-12 15:44:47 回复(1)
梦境迷离头像 梦境迷离
2的10次方1024
发表于 2017-12-08 23:56:43 回复(0)
牛客号2333头像 牛客号2333 

 二分查找，时间复杂度为O(log2n)

编辑于 2022-02-28 15:56:26 回复(0)
任我游头像 任我游

这里可以利用完全二叉树的思想，所有的节点个数为1000个，求树的最小高度的问题。。。当高度为10时，能查找到1023个元素。
编辑于 2017-07-30 14:57:23 回复(3)
BrainerGao头像 BrainerGao
二分查找，遇到这种题，直接计算2的多少次方可以大于指定数值
发表于 2020-02-02 22:28:51 回复(0)
_Foozi头像 _Foozi
log2n + 1，需要向上取整
发表于 2021-11-02 11:39:31 回复(0)
牛客707235628号头像 牛客707235628号
1024是2的10次方，刚好；9次的话，是512，查不全。
发表于 2020-05-21 16:33:04 回复(0)
顾宁头像 顾宁
最多次数既为最坏情况 二分法每次选取一半数据 最大既为log 2 n 大于数据个数时 n取10
发表于 2020-04-07 17:05:00 回复(0)
昵称就是这了头像 昵称就是这了

对数向上取整

发表于 2019-11-21 20:55:59 回复(0)
提交观点

问题信息

查找
上传者：阿奻_
难度：
11条回答 11395浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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