java - 下面的二分查找代码是正确的还是不正确的？ (来自 Programming Interviews Exposed 一书)

Question

书上二分查找的递归版本:

int binarySearch(int[] array, int target) throws BSException { return int binarySearch(int[] array, int target) throws BSException { 
    return binarySearch(array, target, 0, array.length-1);
}

int binarySearch( int[] array, int target, int lower, int upper ) throws BSException {
    int center, range;

    range = upper - lower; 

    if( range < 0 ){
        throw new BSException("Limits reversed");
    } else if( range == 0 && array[lower] != target ){ 
        throw new BSException("Element not in array");
    }

    if( array[lower] > array[upper] ){
        throw new BSException("Array not sorted"); 
    }
    center = ((range)/2) + lower; 
    if( target == array[center] ){
        return center;
    } else if( target < array[center] ){
        return binarySearch( array, target, lower, center - 1 ); 
    } 
    else {
        return binarySearch( array, target, center + 1, upper ); 
    }
}

和迭代版本:

while( true ){
    range = upper - lower;

    if( range == 0 && array[lower] != target ){
        throw new BSException("Element not in array");
    }

关于所有其他算法书籍，包括 Donald Knuth 的 TAOCP、算法设计手册、Programming Pearl 等，都有“有效案例”

while (low <= high) {
    // ...
}
return -1;  // not found

或 low > high 的“未找到”案例:

if (low > high) return -1;   // not found

但是Programming Interviews Exposed这本书中的递归和迭代算法使用了low > high (意思是 range < 0 )作为 BSException("Limits reversed")和 low == high检查“未找到”。现在，如果range实际上小于 0，那么程序会抛出 BSException("Limits reversed") 的异常并且永远无法报告 NotFound。

考虑只有 2 个元素的数组的情况，或者 lower和 upper只包含 2 个元素，比如说

lower is 0
upper is 1
center is (1-0)/2 + 0 = 0

现在，假设target小于 array[center] , 然后 upper = center - 1并且是 -1 , 而 lower保持为 0 .所以我们有 upper < lower含义 range < 0但递归算法将其报告为 BSException("Limits reversed")而不是 NotFound，而迭代没有看到 lower == upper并进一步了解 upper作为-1并使用 array[upper]并且有奇怪的行为？

Answer 1

二分查找的基本前提是一直计算到lower <= upper为止。被满足。这意味着 ( upper-lower ) (在您的示例中是 range )不能为负数。如果它是负数(upper 小于lower)你停止处理并且return -1指示Not found或抛出 exception (如您的示例所示)。

Limits Reversed 对调用者没有意义。因此，将其更改为抛出异常 Not found .

if (range < 0 || (range == 0 && array[lower] != target)) {
    throw new BSException("Element not in array");
}

但是，可能会出现此递归函数的调用者错误地互换了下层和上层的情况。在那种情况下，它会说 Not found而不是 Limits reversed但是，没关系。让调用者调查并找出他的代码中的错误。