java二进制搜索不会结束
基本上,我知道对有序列表执行二进制搜索只是为了让它工作,所以我使用的列表如下:
Integer[] x = {1, 2, 3, 4, 5, 6};
所以基本上它可以找到一个整数,但是当我输入一个不在列表中的值时,它似乎不会结束!这是我的密码:
public static <K extends Comparable<K>> boolean binarySearch(K[] list, K item) {
int start = 0;
int last = list.length - 1;
while(start <= last) {
int middle = (start + last) / 2;
if(list[middle].equals(item))
return true;
else {
if(item.compareTo(list[middle]) < 0)
last = middle--;
else
start = middle++;
}
}
return false;
}
# 1 楼答案
如果不想,您不需要实现自己的二进制搜索算法。Arrays类提供了几种不同的实现,您可能会在那里找到合适的实现。对于提到的示例,有一个用于
int[]
{a2}的示例和一个用于可能感兴趣的泛型对象int binarySearch(T[] a, T key, Comparator c)# 2 楼答案
问题在于确定
middle
的部分。在start = 4
、last = 5
、middle
始终为4
的情况下。在所有这样的情况下都会发生无休止的循环,其中.5
被截断,因为这是一个int
# 3 楼答案
罪犯是
last = middle ;
和start = middle++;
后增量和后减量运算符返回操作数的上一个值,而不是更新后的值。因此,当您调用
last = middle ;
时,这将有效地将middle
减少1,并将last
设置为middle
,而不是middle-1
让我们考虑搜索7,看看它为什么进入无限循环。该项始终位于中间元素之后,因此
start
被设置为middle
,它最终将是数组的最后一个元素。但由于start = middle
,它总是低于或等于last
;因此你永远不会退出。我们已经到了一个反复start = last = middle
的状态,我们永远无法退出它在这里,您不应该使用这些操作符:当要搜索的项位于中间元素之前时,让
last = middle-1;
;当要搜索的项位于中间元素之后时,让start = middle+1;