首页 > 试题广场 >

有关折半查找代码不正确的是

[不定项选择题]
下面是折半查找的实现，data是按升序排列的数据，x是查找下标，y是查找的上标（左右都是闭区间），
v是查找的数值，返回v在data的索引，若没找到返回-1。代码不正确是____。 
public int bsearch(int[] data, int x, int y, int v) {
    int m;
    while(x<y){ //1
        m = x + (y-x)/2; //2
        if(data[m] == v) return m; //3
        else if(data[m] > v) y = m; //4
        else x = m; //5
    }
    return -1; //6
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
查看答案及解析
添加回答
guanjian头像 guanjian
1.标准实现
publicintbsearch(int[] data, intx, inty, intv) {
    intm;
       while (x<=y){   //1
        m = x + (y-x)/2; //2
        if(data[m] == v) returnm; //3
        else if (data[m] > v) y = m-1;   //4
          else x = m+1;   //5
    }
    return-1; //6
}

发表于 2015-09-03 09:17:02 回复(0)
philian头像 philian
如果不包含上界
int BinSearch(int[] data, int lo, int hi,int e)
{
	while (lo < hi)
	{
		int mid = (lo + hi) / 2;
		if (data[mid]>e)
			hi = mid;
		else 
			lo = mid+1;
	}
	return --lo;//返回的--lo是不大于e的元素的最大秩，而lo是大于e的元素的最小秩
}
如果包含上界
int BinSearch(int[] data, int lo, int hi,int e)
{
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (data[mid]>e)
			hi = mid-1;
		else 
			lo = mid+1;
	}
	return --lo;//返回的--lo是不大于e的元素的最大秩，而lo是大于e的元素的最小秩
}

发表于 2016-09-11 17:11:55 回复(0)
xiao_lai头像 xiao_lai
二分查找主要分为两种形式：
1. 区间左开右闭。elsex = m＋1; //5
2. 区间左右都闭合 while(x<＝y){ //1  elseif(data[m] > v) y = m－1; //4     elsex = m＋1; //5
发表于 2016-07-24 20:40:44 回复(0)
炮祺泡祺君头像 炮祺泡祺君
共3处不正确：
1. x<y -> x<=y
4. y = m; -> y = m - 1;
5. x = m; -> x = m + 1;
发表于 2018-11-18 19:37:39 回复(0)
Wu_Being头像 Wu_Being 

	while(x<=y) {





	m = x + (y-x)/2; //2





	if(data[m] == v) return m; //3





	else if(data[m] > v) y = m; //4





	else x = m+1; //5





	}





	//这样也可以，题目答案有问题

发表于 2016-03-31 14:37:33 回复(1)
seaway头像 seaway
试一下数组是[1,2,3],下标分别是是012，当你要查找的数值是v=3的时候，你会发现
1、x=0；y=2，v=3，代入后。。。发现m=1；然后data[m]=2，data[m]！=3;因此x=m=1；
2、第二次 x=1；y=2；v=3；代入后发现 m=1； 一直不变 进入死循环

只是把//5的x=m改成了x=m+1，又会发现，while的条件是x<y，不会循环最后一次（像上面那样，x终于好不容易加了1，变成了2，却发现x=y=2，无法通过x<y去执行最后一次）
因此可以同时修改//1和//5就行了

有人会好奇，为什么x=m+1，可是y=m不需要-1，这个问题留给大家去思考。
发表于 2016-03-02 11:03:06 回复(0)
TaskMachine头像 TaskMachine
这道题考的应该是极限状态，5的代码应该为else x = m+1;因为data[m]已经不用考虑了，应该从data[m+1]开始迭代，以上是我的想法。
发表于 2015-08-26 19:38:49 回复(1)
lxs头像 lxs
上下标没有写清楚，题目所指的应该是[x,y),这样5应该是m-1
而在下标为[x,y]的情况下，1,4,5都是有问题的。。。。正确版本应该是这样吧
while(x<=y) {
        m = x + (y-x)/2; //2
        if(data[m] == v) return m; //3
        else if(data[m] > v) y = m-1; //4
        else x = m+1; //5
    }

补充：这里下标是个坑，记住上限有没有包含就可以对付1,4,5处的问题（熟记理解两个版本的代码区别），然后是2，写成x+(y-x)/2是防止xy都很大的情况下x+y越界。这样的话应对二分查找应该够了
编辑于 2015-09-04 15:59:20 回复(14)
牛客192816号头像 牛客192816号
不是1吗？x等于y怎么办？
发表于 2015-08-26 21:09:36 回复(2)
张元亮头像 张元亮
y = x + 1 && data[x] < v 的时候，x = m 会导致死循环
发表于 2015-08-26 21:59:42 回复(2)
七。小H头像 七。小H
我认为这道题有很多错误！首先4处和5处的应该是y=m-1和x=m+1,如果不这样写的话，必定会造成一些序列出现死循环。如：{2, 6, 8, 10, 13, 25, 36, 45, 53, 76, 88, 100, 127}。如果四处已经更改。
如果1处保持不变，则6处是错误的。6处这时不能直接返回-1，还要进行一次比较。
如果6处保持不变，则1处应该是x<=y。

你们怎么认为啊？
发表于 2015-11-18 14:18:23 回复(1)
项非田头像 项非田
二分查找需要分为两种：左闭右开、左闭右闭
它决定了边界条件是x<y还是x<=y ！
对于一个n元素的数组
1.左闭右开需要传参0和n，也就是右端点不可达，这样边界条件就是x<y，因为一旦二者相等，根据右端点不可达，循环应该立即停止
2.左闭右闭需要传参0和n-1，边界条件是x<=y，二者相等说明该点仍然可取
发表于 2019-07-22 22:45:03 回复(1)
青山崖野头像 青山崖野
折半查找:
算法：low=1；high=n；
      while(low<=high)              //等号“=”不能丢
      {
          mid=（low+high）/2;
          if(key<a[mid])
              high=mid-1;              //注意为啥“-1”
          else if(key>a[mid)
              low=mid+1;               //为啥“+1”
          else
              return mid
       }
       return 0;
若low=mid+1;
例：{1,2,3,4,5,6,7,8,9}，key=9；
1--mid=(1+9)/2=5,low=mid+1=6
2--mid=(6+9)/2=7,low=mid+1=7
3--mid=(7+9)/2=8,low=mid+1=9
4--a[mid]=key

若low=mid；
1--mid=(1+9)/2=5,low=mid=5
2--mid=(5+9)/2=7,low=mid=7
3--mid=(7+9)/2=8,low=mid=8
4--mid=(8+9)/2=8 自此陷入死循环
发表于 2017-04-10 21:10:23 回复(2)
sponge_wxy头像 sponge_wxy 

	publicintbsearch(int[] data, intx, inty, intv) {





	    intm;





	    while(x<y){ //1





	        m = x + (y-x)/2; //2





	        if(data[m] == v) returnm; //3





	        elseif(data[m] > v) y = m; //4





	        elsex = m; //5





	    }





	    return-1; //6





	}





	解析：首先对于这种情况，错误的地方在5处，应将其改为x=m+1,因为m=x+(y-x)/2，m的取值是靠近x的，因此必须保证x的下一次的取值要大于m,





	因此将5处改成x=m+1即可。





	 





	另外对于下面这种情况：





	

	

		publicintbsearch(int[] data, intx, inty, intv) {
	


	

		    intm;
	


	

		    while(x<y){ //1
	


	

		        m = y - (y-x)/2; 
	


	

		        if(data[m] == v) returnm; //3
	


	

		        elseif(data[m] > v) y = m; //4
	


	

		        elsex = m; //5
	


	

		    }
	


	

		    return-1; //6
	


	

		}
	


	

		
	


	

		这种情况下m的取值是靠近y的，因此我们必须保证y在下一次的取值是要小于m的，因此将4处改成y=m-1即可
	


	

		 
	


	

		第三种情况便是：
	


	

		while(x<=y) {
	


	

		    m = x + (y-x)/2; // 1 
	


	

		    m = y - (y-x)/2; // 2 
	


	

		    if(condition1(m)) return m; 
	


	

		    else if(condition2(m)) y = m - 1; 
	


	

		    else x = m + 1;
	


	

		}
	


	

		return -1;
	


	

		
	


	

		总之，二分是存在三种情况的，一种为查找某一值x是否存在，另一种为查找大于等于某一值的最小值，另另一种为查找小于等于某一值的最大值，
	


	

		自己慢慢体会吧，还是蛮好理解的。
发表于 2016-05-17 12:14:50 回复(0)
GoAshore头像 GoAshore
1处应该是x<=y，不然会有边界值取不到。
发表于 2022-12-06 20:56:14 回复(0)
m0rning头像 m0rning
int Binary_Search(SeqList L, ElemType key){ int low = 0,high = L.lengh -1,mid; while (low <= high){ mid = (low + high)/2; if (L.elem [mid] = key) return midm; else if (L.elem [mid] > key) high = mid - 1; else low = mid + 1; } return -1; }
发表于 2021-04-05 19:37:18 回复(0)
LauZyHou头像 LauZyHou
首先5肯定不对，因为除法是向下取整的，下标9+10再除以2还是9，所以必须x=m+1。 其次1肯定不对，还是9+10再除以2的例子，x变成10之后10也要进行比较，所以必须x<=y。 最后4肯定不对，因为在x=y的时候m=x=y，如果这时候数据比要查找的值大，会进入死循环，所以必须y=m-1。
发表于 2020-05-18 07:59:07 回复(0)
C.201903151809497头像 C.201903151809497
正确的写法应该是这样的：
function binary_find(arr, val) {
    if(arr == null || arr.length == 0 || val == null) return -1;
    var start = 0;
    var end = arr.length - 1;
    while(start <= end) {
        var middle = start + Math.floor((end - start) / 2);
        if(val == arr[middle]) {
            return middle;
        } else if(val > arr[middle]) {
            start = middle + 1;
        } else if(val < arr[middle]) {
            end = middle - 1;
        }
    }
    return -1;
}
可以综合题目代码比较，就可以判断出哪些代码段有错误，选出合适的选项
发表于 2020-04-07 10:38:18 回复(0)
牛客913265909号头像 牛客913265909号
elseif(data[m] > v) y = m-1; //4
        elsex = m+1; //5
这两处的改动是为了
 while(x<=y){ //1做的铺垫，不然会因为出现x=y而使程序陷入死循环。
发表于 2020-03-22 09:53:52 回复(0)
秋天以北头像 秋天以北
public int bsearch(int[] data,int x,int y,int v) {
   int m;
   while(x<y){//1
       m = x + (y-x)/2;//2
       if(data[m] == v) return m;//3
       else if(data[m] > v) y = m;//4
       else x = m;//5
   }
   return -1;//6
}
其中1错误是没有处理到序列长度为1的情况
4和5错误是因为y=m或x=m在y-x=1的情况下时m值恒为x，而根据循环里的判断，此时data[m]<v,x=m;由此while陷入死循环，正确的做法是当上限值大于v或下限值小于v时，让上限下标减一或下限下标加一，即可解决死循环问题。
发表于 2020-03-03 14:14:47 回复(0)
提交观点

问题信息

查找
来自：楚楚街2016在线笔试练习卷
难度：
47条回答 13332浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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