首页 > 试题广场 >

已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用

[单选题]

已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个 L中 不存在的元素，则 关键字的 比较次数最多是（） 

  • 4
  • 5
  • 6
  • 7
查看正确选项
添加回答
JonnyTang头像 JonnyTang
一次找到最边界的那一个数的情况下是最多次数的。
eg:  找的是第16个数
(0+15)/2   7     　第1次
(8+15)/2   11   　第2次
(12+15)/2  13 　第３次
(14+15)/2 14     第４次
(15+15)/2  15   第５次
发表于 2016-12-25 18:06:14 回复(0)
我要你的自然97头像 我要你的自然97
16个二叉排序树的深度为5，查找一个不存在的最多查到最后一层，即5
发表于 2018-05-13 12:03:52 回复(1)
sunlight_run头像 sunlight_run


在本题中，假设查找的数据为20，那么就是按图中箭头挨个查找，查到15还没有 查到，但此时已经查了5次。
最少为4次的情况是从7开始，往左查询。。。。。可以按图试试。。。。。。
发表于 2017-07-01 15:17:35 回复(0)
striving_qi头像 striving_qi
对于二分查找，查找成功与查找不成功，最坏的情况下，都需要比较[log2n]+1（向下取整），或者[log2(n+1)](向上取整)，其实就是树的深度公式
发表于 2017-08-11 16:20:23 回复(0)
philian头像 philian

答案给的不对，最多应该是5次，最少是4次
发表于 2016-12-17 09:50:40 回复(4)
放开那个女孩，我来头像 放开那个女孩，我来

折半查找在查找不成功时和给定值进行关键字比较的次数最多为树的高度log2n＋1


发表于 2018-09-14 17:05:47 回复(1)
BrainerGao头像 BrainerGao

折半查找一个有序表中不存在的元素，最多查找log2n+1次，即二叉排序树的深度。注：log2n为logn/log2,以2为底

发表于 2017-04-17 21:49:20 回复(0)
牛客952624550号头像 牛客952624550号
深度为k的二叉树至多有2^k -1个节点所以2^k- 1 >= 16 即 k>=log2(17)得到 k > 4 因此 k为5
发表于 2021-11-16 21:43:59 回复(0)
J-Young头像 J-Young
虽然二分查找的逻辑很简单，但是真正实际操作起来很可能就出现问题。
第一次:mid=(0+15)/2 = 7. 我们对比下标为7的数值与目标数值的大小。
第二次(我们往分区数据多的一半来查找):mid = (8+15)/2 = 11.
第三次:mid = (12+15)/2 = 13
第四次:mid=(14+15)/2 = 14
第五次：mid=(15+15)/2 = 15
发表于 2021-06-17 15:39:57 回复(0)
我头发茂盛头像 我头发茂盛
log2(16) + 1 = 5 (也就是二叉树最小深度+1)
发表于 2021-05-24 19:51:20 回复(0)
舞动的小胖子头像 舞动的小胖子
从中间向左查是4次，向右查是5次 注意 人家问的是最多
发表于 2019-06-29 22:57:54 回复(0)
玄名观头像 玄名观
发表于 2016-12-05 21:16:29 回复(1)
Wilbur.头像 Wilbur.
搞错了，最开始往剩余8元素的部分查找
发表于 2022-08-25 19:31:09 回复(0)
牛客218196695号头像 牛客218196695号
第一次（0+15）/2 ；
第二次 （0+6）/2；
第三次 （0+2）/2；
第四次 （0+1）/2；
第五次 （0+0）/2；
发表于 2020-06-25 18:54:56 回复(0)
牛客爸爸保我进tx头像 牛客爸爸保我进tx
2^n<16> n=5
发表于 2020-03-12 22:25:02 回复(0)
水果~达舒头像 水果~达舒
前面大神是不是弄错了，第一个查找的不是第八位吗？？ （1+16）/2＝8
发表于 2017-03-20 09:29:31 回复(5)
提交观点

问题信息

查找
上传者：城市里的养猫者
难度：
16条回答 27699浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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