Java：二进制搜索实现无法使用延迟检测相等性

Question

我正在尝试实施二进制搜索 Java 版本。从维基百科 http://en.wikipedia.org/wiki/Binary_search_algorithm#Deferred_detection_of_equality 我注意到延迟检测相等版本。它正在使用该算法。但是，当我尝试像这样更改 if 条件表达式时：

    public int bsearch1(int[] numbers, int key, int start){
    int L = start, R = numbers.length - 1;
    while(L < R){
        //find the mid point value
        int mid = (L + R) / 2;
        if (numbers[mid] >key){
            //move to left
            R = mid - 1;
        } else{
            // move to right, here numbers[mid] <= key
            L = mid;
        }
    }
    return (L == R && numbers[L] == key) ? L : -1;
}

运行不正常，进入死循环。你们有什么想法吗？太感谢了。

Answer 1

您错过了您 link 访问的 Wiki 中 assert 的效果。

它指出：

code must guarantee the interval is reduced at each iteration

如果您的 mid >= R，您必须退出。

已添加

Wiki 实际上有点误导，因为它表明仅确保 mid < r 就足够了——事实并非如此。您还必须防范 mid == min（假设您有一个 4 条目数组，并且 l = 2 和 r = 3、mid 会变成 2 并停留在那里因为整数数学中的 2 + 3 = 5 和 5 / 2 = 2）。

解决方案是在 / 2 之后向上舍入，这可以通过以下方式轻松实现：

  int mid = (l + r + 1) / 2;

最终更正和整理的代码有点像这样：

public int binarySearch(int[] numbers, int key, int start) {
    int l = start, r = numbers.length - 1;
    while (l < r) {
        //find the mid point value
        int mid = (l + r + 1) / 2;
        if (numbers[mid] > key) {
            //move to left
            r = mid - 1;
        } else {
            // move to right, here numbers[mid] <= key
            l = mid;
        }
    }
    return (l == r && numbers[l] == key) ? l : -1;
}

public void test() {
    int[] numbers = new int[]{1, 2, 5, 6};
    for (int i = 0; i < 9; i++) {
        System.out.println("Searching for " + i);
        System.out.println("Found at " + binarySearch(numbers, i, 0));
    }
}

有一个非常相似的算法 here 表明正确的方法更像是：

public int binarySearch(int[] numbers, int key) {
    int low = 0, high = numbers.length;
    while (low < high) {
        int mid = (low + high) / 2;
        if (numbers[mid] < key) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low < numbers.length && numbers[low] == key ? low : -1;
}

这对 high = max + 1 的边界条件采用了一种略有不同的方法，并且也很完美。

Java：二进制搜索实现无法使用延迟检测相等性

Java: Binary Search Implementation not working using Deferred detection of equality

java

search

binary