java - 二进制搜索Java错误

我得到了这种二进制搜索来找出问题所在。有一条注释掉了一行，到目前为止，我唯一能想到的就是删除该行，因为我认为这不是必需的。除此之外，我想不出有什么遗漏-确实有明显的错误之处吗？

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，所以即使条件为1，也可以退出循环，因为条件为low < high，并且返回false。

问题来自middle = low + (high-low)/2;使用int并将被四舍五入的事实。