java二进制搜索不会结束

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

如果不想，您不需要实现自己的二进制搜索算法。Arrays类提供了几种不同的实现，您可能会在那里找到合适的实现。对于提到的示例，有一个用于int[]{a2}的示例和一个用于可能感兴趣的泛型对象int binarySearch(T[] a, T key, Comparator c)

Answer 2

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

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