首页 > 试题广场 >

折半查找有序表（4,6,10,12,20,30,50,70,

[单选题]

折半查找有序表（4,6,10,12,20,30,50,70,88,100）。若查找表中元素58，则它将依次与表中哪些元素比较大小，查找结果失败（） 

  • 20，50
  • 30，88，70，50
  • 30，88，50
  • 20，70，30，50
查看答案及解析
添加回答
推荐
丨太阳与月亮丨头像 丨太阳与月亮丨
D
10个数首先和中间值20比较，58比20***择右边，右边5个数选择中间值70,58比70小，选择左边，左边两个数中间值30进行比较，58比30***择右边，右边一个数50,58比50大，没有找到
编辑于 2017-03-03 10:02:28 回复(4)
我们都是大好青年头像 我们都是大好青年
注意第一个数值的选择应靠前
发表于 2018-07-09 12:08:35 回复(0)
AvalonGwenda头像 AvalonGwenda
经典二分查找中确定中间值的代码是 
middle = (low+high)/2
因此这里应当取20为中间值

发表于 2019-11-08 09:51:56 回复(0)
牛客882122502号头像 牛客882122502号 
int BinSearch(vector<int>R, int key)
{
    int low = 0, high = R.size()-1, mid;
    while (low <= high)
    {
        mid = low + (high-low)/2;
        //或是mid = low + ((high - low)>>1)
        //采用mid = (low + high)/2有可能导致溢出
        printf("查找的元素为%d,索引为%d\n",R[mid],mid);
        if (R[mid] == key)
        {
            return mid + 1;
        }
        if (R[mid] > key)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return 0;
}
采用二分查找法，
第一轮两端点为[0,9]，mid为4，58大于20，区间右移
第二轮两端点为[5,9]，mid为7，58小于70，区间左移
第三轮两端点为[5,6]，mid为5，58大于30，区间右移
第四轮两端点为[6,6]，mid为6，58大于50，区间右移
因为此时high(6)<low(7)，查找失败，跳出循环
编辑于 2021-06-13 08:33:42 回复(0)
Wilbur.头像 Wilbur.
取中间值，也就是首尾下标之和除以二
发表于 2022-08-25 19:33:43 回复(0)
FunkyAnsi头像 FunkyAnsi
<p>注意，取下标方式为：从0开始到9（0+9）/2向下取整</p>
发表于 2020-11-04 16:12:19 回复(0)
是怡不是鱼头像 是怡不是鱼
二分法查找中，折半后去下整数，同时，下一次查找不包含上一次查找的数字，从其前一个或后一个开始
发表于 2020-05-20 09:43:04 回复(0)
Wao201908171243900头像 Wao201908171243900
折半查找就是二分查找 每次二分比较的位置 肉眼计算：length/2，向下取整 计算机代码计算：（length-1）/2，向下取整
发表于 2020-04-10 11:26:20 回复(0)
顾宁头像 顾宁
int middle=（low+high）/2 取整
发表于 2020-04-07 17:25:19 回复(0)
Lance217头像 Lance217
首先取中间的20
然后去30-100之间的70
然后取30 - 50之间的30
最后50
发表于 2020-03-20 06:26:49 回复(0)
牛客287369450号头像 牛客287369450号
发表于 2023-02-22 19:18:54 回复(0)
卡伦头像 卡伦
比元素小取小，比元素大取大
发表于 2020-03-19 12:22:52 回复(0)
可能会吧、头像 可能会吧、

每次二分比较的位置

肉眼计算：length/2，向下取整

计算机代码计算：（length-1）/2，向下取整


发表于 2020-02-05 14:25:55 回复(0)
丶201906020946805头像 丶201906020946805
二分是根据（length/2）还是（(length-1)/2），感觉在这种是非面前吃亏了不知多少次，有时候真怀疑是自己脑子的问题
发表于 2019-09-08 23:04:03 回复(0)
牛客687272号头像 牛客687272号
每个子数组的中位下标：(长度 - 1)/2
编辑于 2018-04-07 21:33:10 回复(0)
Yummy蛋卷头像 Yummy蛋卷
感觉怪怪的 索引定为0 1 2... 9 第一次和索引为9//2=4的数20比较 第二次和索引为（4+9）//2=6的数50比较 第三次和.. 答案d一会取下中位数 一会取上中位数 不懂
发表于 2018-03-11 00:08:09 回复(2)
牛客2143162号头像 牛客2143162号
d
发表于 2017-05-11 19:31:59 回复(0)
Feater头像 Feater
d
发表于 2017-02-25 23:37:07 回复(0)
Dream.Ing头像 Dream.Ing
d
发表于 2017-02-15 16:06:25 回复(0)
kasnet头像 kasnet
D
发表于 2016-12-05 22:40:44 回复(0)
提交观点

问题信息

查找
来自：凤凰网2017秋招研发...
上传者：牛100
难度：
20条回答 24701浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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