首页 > 试题广场 >

用二分法查找长度为10的、排好序的线性表，查找不成功时，最多

[单选题]
用二分法查找长度为10的、排好序的线性表，查找不成功时，最多需要比较多少次？ 
  • 3
  • 4
  • 5
  • 6
查看答案及解析
添加回答
木棉今生头像 木棉今生
B
二分查找，可以用二叉判定树，查找不成功的次数不超过判定树的深度，而树的深度为|_log2n_|+1
编辑于 2015-09-15 10:52:44 回复(0)
香蕉牛奶头像 香蕉牛奶
B
4次。假设线性表里是非递减排好序的10~19这10个数字，查找的是20，显然查找不成功。根据算法，第一次比较的是下标为 (0+9)/2=4 的元素14，第二次比较的是下标为 (5+9)/2=7 的元素17，第三次比较的是下标为 (8+9)/2=8 的元素18，第四次比较的是下标为 (9+9)/2=9 的元素19，算法结束，因此共比较4次。如下图：

编辑于 2015-01-28 14:53:46 回复(3)
Aix码哥头像 Aix码哥
B
8<10<16,而log16=4
发表于 2015-07-01 16:37:06 回复(0)
我就用这个名字了头像 我就用这个名字了
二分查找，可以用二叉判定树，查找不成功的次数不超过判定树的深度，即（log 2 n）+1，其中 log 2 n向下取整
log 2 10向下取整就是3，3+1=4.
发表于 2016-05-18 09:08:53 回复(0)
莲之鱼头像 莲之鱼
刚开始算出来是3，后来才找到原因，原来第一次没找到后，若是往少的一半去找，就会是3次。往大方向找就是4次。
比如0 1 2 3 4 5 6 7 8 9 查找-1，可能就是先是比较4 再是1 再是 0  三次
但是若是查找10 就是，先比较4 再比较7 再比较8 再比较 9  四次

发表于 2016-08-29 17:37:46 回复(0)
codersong头像 codersong
就是树的高度[logn]+1
发表于 2015-10-09 11:14:00 回复(0)
宋佑廉头像 宋佑廉
二分查找，可以用二叉判定树，查找不成功的次数不超过判定树的深度，而树的深度为|_log2n_|+1
发表于 2018-10-28 23:21:52 回复(0)
Ramon_and_I头像 Ramon_and_I
二分查找类似于二叉树每层顶点的个数，2**3 =8 2**4 = 16 显然 8 <10 <16,取上整，所以等于4
发表于 2018-09-22 22:22:05 回复(0)
CodingEnding头像 CodingEnding
计算：⌊log2n⌋+1
发表于 2017-03-15 16:49:04 回复(0)
jackychen头像 jackychen
logn+1
发表于 2017-03-08 11:19:15 回复(0)
Samanlia头像 Samanlia
二分查找，可以用二叉判定树，查找不成功的次数不超过判定树的深度，而树的深度为|_log 2 n_|+1
发表于 2016-08-18 15:49:57 回复(0)
Hello,World!头像 Hello,World!
B
发表于 2015-04-15 21:24:23 回复(0)
国庆头像 国庆
4
发表于 2014-10-13 20:02:05 回复(0)
提交观点

问题信息

查找 360集团
来自：360公司2014校招笔试卷
难度：
13条回答 26316浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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