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

您错过了 assert 的效果在您链接到的 Wiki 中。

它指出:

code must guarantee the interval is reduced at each iteration

如果您的 mid 则必须退出>= R .

已添加

维基实际上有点误导，因为它建议仅仅确保 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而且效果也很完美。