java - BinarySearch 不会结束

Question

所以基本上，我知道对有序列表执行二进制搜索只是为了它起作用，所以这是我正在使用的列表:

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;
}

Answer 1

罪魁祸首是 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;。