我已经得到了这个二分搜索来找出它出了什么问题。有一行被注释掉,到目前为止我唯一能想到的就是删除该行,因为我认为不需要它。除此之外,我想不出有什么遗漏——有什么明显的错误吗?
public boolean search(int val) {
int low = 0;
int high = size-1;
int middle = -1;
boolean found = false;
while (!found && low < high) {
middle = low + (high-low)/2;
if (a[middle] == val)
found = true;
else if (a[middle] < val)
low = middle + 1;
else // (a[middle] > val)
high = middle - 1;
}
return found;
}
最佳答案
假设数组中有 2 个值:[0, 1],并且您查找值 1。让我们运行代码:
int low = 0;
int high = size-1; // high = 1
int middle = -1;
boolean found = false;
while (!found && low < high) {
middle = low + (high-low)/2; // middle = 0 + (1-0) / 2 = 0
if (a[middle] == val) // FALSE (because a[0] = 0)
found = true;
else if (a[middle] < val) // TRUE (because a[0] = 0 and 0 < 1)
low = middle + 1; // low = 0 + 1 = 1
else // (a[middle] > val)
high = middle - 1;
}
return found;
因为 low = 1,所以你会跳出循环,因为你有一个条件 low < high
即使数组中存在 1,您也会返回 false。
问题来自于 middle = low + (high-low)/2;
使用 int 并将向下舍入。
关于java - Java二分查找错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42418396/