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++;。

Post-递增和post-递减运算符return操作数的前一个值，而不是更新后的值。因此，当您调用 last = middle--; 时，这将有效地将 middle 减 1，并将 last 设置为 middle， 而不是 middle-1.

假设您搜索 7 以了解它为何进入无限循环。该项目始终位于中间元素之后，因此 start 设置为 middle，最终将成为数组的最后一个元素。但是由于start = middle，总是小于等于last；因此你永远不会退出。我们已经达到了 start = last = middle 反复并且永远无法退出的状态。

在这里，您不应该使用这些运算符：当要搜索的项目在中间元素之前时，让 last = middle-1;；当要搜索的项目在中间元素之后时，令 start = middle+1;.

Answer 2

问题出在您确定 middle 的部分。在 start = 4、last = 5 的情况下，middle 将始终是 4。在像这样的所有情况下都会发生无限循环，其中 .5 被截断，因为这是一个 int .

Answer 3

如果您不想，则无需实现自己的二分查找算法。可能感兴趣的Arrays class provides several different implementations and chances are that you will find a suitable implementation there. For the examples mentioned there is one for int[] int binarySearch(int[] a, int key) and one for generic objects int binarySearch(T[] a, T key, Comparator c)。

BinarySearch 不会结束

BinarySearch won't end

java

binary-search