java我的二进制搜索怎么了?
我刚刚开始学习Java(这是我第一次用它编程)。如果print语句是(纯粹出于测试目的),那么代码会重复输出mid,而不会改变它。我想了好几个小时,还是想不出来。非常感谢您的帮助
/*class containing binary search algorithm*/
public class BinarySearch {
/*conducts a binary search as specified by user*/
public static int binarySearch(int queryValue, int[] list) {
int length = list.length;
/*last point of list*/
int top = length-1;
/*first point of list*/
int bottom = 0;
/*starting midpoint of list*/
int mid = (int)Math.round((top + bottom)/2);
/*binary search*/
while(bottom < top) {
if((int)queryValue == (int)list[mid]) {
return mid;
}
else if(queryValue > list[mid]) {
bottom = mid;
mid = (int)Math.round((top + bottom) / 2);
StdOut.print(mid);
}
else {
top = mid;
mid = (top + bottom) / 2;
}
}
/*returns -1 if user value not found*/
return -1;
}
}
# 1 楼答案
如果您提供用于测试的数据会更好
至于现在,我看到对于以下输入,它将挂起:
binarySearch(9, new int[] {1,2,3,4,5,6,7,8,9})
mid将是7
这是因为(7+8)/2=7,因为您使用int
尝试替换:
mid = (int)Math.round((top + bottom) / 2);
用
mid = (int)Math.round((top + bottom) / 2.0);
它将解决这个问题
祝你好运
更新代码以考虑边缘情况: