首页 > 试题广场 >

一个长度为32的有序表，若采用二分查找一个不存在的元素，则比

[单选题]
一个长度为32的有序表，若采用二分查找一个不存在的元素，则比较次数最多是__？ 
  • 4
  • 5
  • 6
  • 7
查看正确选项
添加回答
水煮鱼头像 水煮鱼

最方面的方法是建立一个判定树。

现在有11个数：（第1行是索引，第2行是数）

0 1 2 3 4 5 6 7 8 9 10
7 10 13 16 19 29 32 33 37 41 43

判定树：

圆形节点表示查找成功的节点，方形的是查找不成功的节点。

判定树展示了二叉查找的过程。

有：

查找成功的最少次数：1
查找成功的最多次数：4

查找成功的平均次数：(1*1+2*2+3*4+4*4) / (1+2+4+4) = 3

查找不成功的最少次数：3
查找不成功的最多次数：4
查找不成功的平均次数：（3*4+4*8）/(4+8) = 11/3

发表于 2017-09-29 15:44:23 回复(0)
牛客981559号头像 牛客981559号
最坏无外乎分到最后
32 1
16 1
8 1
4 1
2 这时候比较最坏比较2次一共6次（ 除非里面必含所查元素是5次）
发表于 2016-08-22 16:40:21 回复(1)
chouchou-小宠头像 chouchou-小宠
如果查找存在的元素，最多需要的比较次数是几次？
发表于 2017-04-19 16:22:43 回复(0)
兔子的救兵头像 兔子的救兵
2^5=32
发表于 2015-09-14 13:27:21 回复(0)
峰风头像 峰风
这题其实是考察完全二叉树的深度问题，比较次数也就是深度，只含有一个节点的时候深度为1，假设深度为k，则有2^k-1>=n>2^(k-1)-1,其中2^k-1对应深度为k的满二叉树对应节点数，那么等价于2^k>=（n+1）>2^(k-1)，不等式两边同时取log，k>=log(n+1)>(k-1),此时k等于log(n+1)向上取整数，因此log（32+1）向上取整为6
发表于 2015-09-17 10:15:42 回复(1)
Bruteforce头像 Bruteforce
查找不存在的比存在的多比较一次，存在的次数是树的深度5因此不存在的是6。
发表于 2016-02-29 23:34:35 回复(8)
lostcode头像 lostcode
用二分查找的判定树来解决，建成一个完全二叉树，32个元素的树高度为6
发表于 2015-10-03 14:40:36 回复(8)
ryl头像 ryl
32个元素，用二叉树表示需要6层(五层一共2^5-1=31个元素)，当然是6次比较。
编辑于 2016-03-28 19:40:37 回复(0)
liuhuoer头像 liuhuoer

折半查找数组长度为奇数时最多查找㏒ n次，偶数时最多查找㏒ n +1次。

发表于 2019-02-20 09:26:20 回复(0)
loveCoding头像 loveCoding
找不到元素需要logn + 1次，此题n为32， 故答案应该是6.
发表于 2015-09-14 15:03:49 回复(0)
java牛马头像 java牛马
log2n   +1    （log2n 向下取整）
发表于 2017-07-15 10:05:27 回复(0)
9573头像 9573
编辑于 2024-04-19 18:20:02 回复(0)
_Foozi头像 _Foozi
log2(32)+1 = 5+1=6
发表于 2021-11-02 11:40:36 回复(0)
noweinowei头像 noweinowei
判定书，包含不存在的叶子节点
发表于 2021-03-12 08:12:59 回复(0)
刷牛客的小熊猫很无聊头像 刷牛客的小熊猫很无聊
log2n(向下取整) + 1 Log2(n+1)向上取整
发表于 2020-11-15 12:31:06 回复(0)
不做人了头像 不做人了
不存在会多比较一次
发表于 2020-05-27 12:28:45 回复(0)
Lance217头像 Lance217
2^5是32，但找的是不存在的元素，所以5+1为6
发表于 2020-03-20 06:36:27 回复(0)
花开半夏☞培培头像 花开半夏☞培培
因为是二分查找，32个数字（0-31），第一次比较16，第二次为8，......4,2,1,0，所以最多6次，到叶子节点，即求树的深度。
发表于 2019-07-30 08:45:15 回复(0)
一包薯条呸呸头像 一包薯条呸呸
二分查找成功平均查找长度为 log2(n+1)-1 由于是失败 所以+1次  为 log2(n+1)  把N带进去等于6
发表于 2018-07-30 21:47:02 回复(0)
rppp头像 rppp
查找不存在的比存在的多一次，存在的次数是5 ，因此不存在的是6
发表于 2017-07-20 09:17:23 回复(0)
提交观点

问题信息

查找
来自：楚楚街2016在线笔试练习卷
难度：
25条回答 19497浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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