首页 > 试题广场 >

折半查找有序表(2,10,25,35,40,65,70,73

[单选题]
折半查找有序表(2,10,25,35,40,65,70,73,75,81,82,88,100)， 若查找元素75，需依次与表中元素（ ）进行比较。
  • 70, 81, 75
  • 70, 82, 75
  • 70, 82, 75,73
  • 70,81,73,75
添加回答
推荐
我就是个弟弟1头像 我就是个弟弟1
D：70,81,73,75
索引从0到12，left=0，right=12
1、mid=6，与70比较，比75小，left=mid+1=7，right=12
2、mid=9，与81比较，比75大，right=mid-1=8，left=7
3、mid=7，与73比较，比75小，left=mid+1=8，right=8
4、mid=8，与75比较，相等，返回。
编辑于 2019-11-21 14:45:22 回复(1)
白驹之过隙头像 白驹之过隙
选D。
根据题目：待查找数列(2,10,25,35,40,65,70,73,75,81,82,88,100)元素个数为13， 待查找元素为75
  1. 用left指针指向序列的首元素（下标为0），right指针指向序列的尾元素（下标为12），根据折半查找思想，mid=(left+right)/2=6  下标为6的元素为70和待查找元素75做比较，70<75。
  2. 将mid+1赋值给left指针作为新序列的首元素（下标为0），继续mid=(left+right)/2  下标2的元素为81做比较，81>75。
  3. 将mid-1赋值给right指针作为新序列的尾元素，继续运算，mid=0,元素为73，73<75
  4. 找到75元素，比较结束

所以比较的元素为70,81,73,75

发表于 2019-11-20 18:10:18 回复(0)
喜一阿夏头像 喜一阿夏
<p>计算机向左取整</p>
发表于 2020-06-08 15:48:02 回复(0)
成长的小树苗头像 成长的小树苗
选D折半查找 1.先排序从小到大（反这也行） 2.确定上下界，选中间 3.更改上界或者下界（加一减一数据过少），继续找中间 4.直到中间等于所找元素，结束
编辑于 2019-11-20 15:24:15 回复(0)
Jino.头像 Jino.
选D。
索引从0到12，left=0，right=12。
1、mid=(left+right)/2=6，与70比较，70<75，left=mid+1=7，right=12
2、mid=(left+right)/2=9.5，向下取整索引为9，则与81比较，81>75，因此right=mid-1=8，left=7
3、mid=(left+right)/2=7.5，向下取整索引为7，与73比较，73<75，left=mid+1=8，right=8
4、mid=(left+right)/2=8，与75比较，75=75，返回。
编辑于 2019-11-20 21:57:08 回复(2)
Meloin头像 Meloin
折半查找 记住向下取整！
发表于 2020-04-05 12:55:24 回复(0)
GlowingEnzo头像 GlowingEnzo
取mid的时候是向下取整的。如果mid＞x就下次取0到mid，如果＜就mid到n
编辑于 2024-01-21 21:17:02 回复(0)
Huzh头像 Huzh
<p>二分查找、索引从0开始 mid=（R+L）/2 向下取整数</p>
发表于 2020-07-23 15:35:00 回复(0)
牛客278254125号头像 牛客278254125号
获取二分查找的下标，使用取整算法。
发表于 2020-04-16 14:58:02 回复(0)
Lance217头像 Lance217
计算机中是向左取整，所以当遇到偶数个数时，取左边的，当遇到奇数个数时，取它
发表于 2020-03-20 06:03:00 回复(0)
提交观点

问题信息

查找
上传者：zsw3
难度：
10条回答 3235浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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