首页 > 试题广场 >

已知有序序列b c d e f g q r s t,则在二分

[单选题]
已知有序序列b c d e f g q r s t,则在二分查找关键字b的过程中，先后进行比较的关键字依次是多少?() 
  • f d b
  • f c b
  • g c b
  • g d b
查看正确选项
添加回答
小洁子头像 小洁子
b c d e f g q r s t 二分查找，折半法
① low = 0,high = 9,mid = (low+ high)/2=4,  ∴  'b'比较a[4]='f'，＜,找左边 ( b~e )
② low = 0,high = mid-1 = 3, mid = 3/2=1, ∴ 'b'比较a[1]='c' , ＜，找左边（b~b）
③ low = 0,high = mid -1 = 0,mid = 0,∴ 'b' 比较a[0] = 'b'，找到（若未找到，low=high，也停止查找）
所以比较的顺序就是f c b
编辑于 2016-02-29 13:50:40 回复(1)
PYQ头像 PYQ
注意二分查找每次的下标并不是直接取原来，而是会减一；并且当mid为奇数时，mid/2是向下取整。
发表于 2019-10-09 18:22:27 回复(1)
GS2.0头像 GS2.0
第一次mid=(0+9)/2=4,偏大后向左查找，此时high=mid-1=3，
第二次mid(0+3)/2=1,仍然偏大，继续向左查找，此时high=mid-1=0
第三次mid=(0+0)/2=0,查找到key=f,成功；
所以答案依次为对应的索引：f，c，b
发表于 2018-07-02 13:49:21 回复(0)
chasein头像 chasein
将字符对应成数字，1，2，...，10，转成二叉搜索树，如图
查找1（b），需要比较3次，分别对应5，2，1，即f，c，b
编辑于 2022-12-01 11:35:01 回复(0)
乌拉乌拉嘿哈头像 乌拉乌拉嘿哈

．二分查找的关键在于找到mid､那么：

9/2，取4，则查找f,由于b<f，则范围缩小至：b,c,d,e,

3/2,取1,则查找c､

编辑于 2021-07-29 23:43:38 回复(0)
可为编程头像 可为编程
为什么要减一呢 不减一可以吗
发表于 2023-02-10 09:14:24 回复(0)
Wilbur.头像 Wilbur.
进行二分查找，取中间值
发表于 2022-08-25 19:31:29 回复(0)
_Foozi头像 _Foozi
二分查找，可看做二叉搜索树？
发表于 2021-11-02 08:39:24 回复(2)
恨自己不够强头像 恨自己不够强
找左边，还是找右边，要根据b值的大小
发表于 2019-03-13 16:20:18 回复(0)
提交观点

问题信息

查找
来自：完美世界2016研发工...
上传者：SunburstRun
难度：
9条回答 10522浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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