首页 > 试题广场 >

对一个含有20个元素的有序数组做二分查找，数组起始下标为1，

[单选题]
对一个含有20个元素的有序数组做二分查找，数组起始下标为1，则查找A[2]的比较序列的下标为（） 
  • 9,5,4,2
  • 10,5,2
  • 9,6,2
  • 20,10,5,3,2
查看答案及解析
添加回答
bboyzqh头像 bboyzqh
感觉答案不对呀，求指教！自己计算得出{10，5，2}
(1+20)/2=10、比较A[10]，同时high设置为9，（9+1）/2=5、比较A[5],再次设置high为4，（4+1）/2= 2、比较A[2]
发表于 2016-06-21 23:23:19 回复(6)
花开不败头像 花开不败
(high-low)/2+low = middle; 下标从1开始，因为查找查找A[2]， low始终为1；
（20-1）/2+1=10;
(10-1)/2+1 = 5;
(5-1)/2+1 = 3;
(3-1)/2+1 = 2;
发表于 2016-08-04 18:18:07 回复(2)
王浩浩的快乐生活头像 王浩浩的快乐生活
使用(low+high)/2会有整数溢出的问题（问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时， 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题
发表于 2016-08-09 15:47:10 回复(1)
莽撞人呐头像 莽撞人呐
正确答案应该是 10 5 2 公式直接套：中间数下标 = (起始下标+末尾下标)/2
发表于 2021-07-30 14:44:18 回复(0)
wylhyz头像 wylhyz
int  middle  =  (high - low) / 2 + low ;

选B
发表于 2016-06-23 22:48:39 回复(1)
相当开心果呀头像 相当开心果呀

二分 （左闭右开）

核心代码

while(l < r)
{
    int mid = l + r >> 1;
    if(check(mid) > x) r = mid;
    else l = mid - 1;
}

这样看答案应该是10，5，3，2呀

发表于 2022-03-20 15:15:04 回复(0)
牛客小妞号头像 牛客小妞号
(high-low)/2+low = middle; 下标从1开始，因为查找查找A[2]， low始终为1； （20-1）/2+1=10; (10-1)/2+1 = 5; (5-1)/2+1 = 3; (3-1)/2+1 = 2;
发表于 2021-06-24 23:43:19 回复(0)
stonedreamerno1头像 stonedreamerno1
我也觉得是10 5 2
发表于 2021-06-18 11:21:54 回复(0)
牛客571626675号头像 牛客571626675号
向下取整
发表于 2021-04-14 17:20:28 回复(0)
Plutoweb头像 Plutoweb
我觉得是主要考虑high与low两个指针的问题，既然第一次high=20，low=1；那么第二次high=10，low=1才对啊，然后int  middle  =  (high - low) / 2 + low ;答案B没毛病
发表于 2021-03-11 12:05:50 回复(0)
逸仙爱庆铃头像 逸仙爱庆铃
while(low<=high){  
            //中间位置计算,low+ 最高位置减去最低位置,右移一位,相当于除2.也可以用(high+low)/2  
            int middle=low+((high-low)>>1);  
        //与最中间的数字进行判断,是否相等,相等的话就返回对应的数组下标.  
        if(des==srcArray[middle]){  
            return middle;  
        //如果小于的话则移动最高层的"指针"  
        }else if(des<srcArray[middle]){  
            high=middle-1;  
        //移动最低的"指针"   
        }else{  
            low=middle+1;  
            }

high 和 low 不是都减一了吗
发表于 2016-09-15 20:38:34 回复(0)
java渣洼头像 java渣洼
下标是1开始，一定要看清
发表于 2016-08-02 13:36:57 回复(0)
木.木头像 木.木
选B
发表于 2016-06-21 22:39:26 回复(0)
提交观点

问题信息

查找
来自：乐视2017暑期实习生...
难度：
13条回答 15459浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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