java - 来自已排序数组的 X 的 floor 和 ceil

Question

从已排序的数组中找到数字 X 的底数和底数。例如

a[] = {3, 7, 9, 10, 15}

• if X=2, floor = N/A, ceil = 3
• if X=3, floor = 3, ceil = 3
• if X=4, floor = 3, ceil = 7
• if X=16, floor = 15, ceil = N/A

我想我们大多数人都知道解决方案，即我们可以通过改进的二分查找找到 floor/ceil。但是修改后的二分查找的问题是我们需要处理很多边界条件。但我发现 相同的二进制搜索算法确实有效，但对于 floor 我们只需要写 if low > high return low和 ceil if low > high return high 。如果 floor 返回 -1，则显示 N/A，如果 ceil 返回一个大于数组索引的值，则显示 N/A。

algo for floor:

int floorSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return low;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return floorSearch(a, low, mid-1, x);
    }
    else if(a[mid]<x){
        return floorSearch(a, mid+1, high, x);
    }
    else{
        return mid;
    }
}

and for ceil:

int ceilSearch(int a[], int low, int high, int x)
{
    if(low > high){
        return high;
    }
    int mid = (low+high)/2;
    if(a[mid]>x){
        return ceilSearch(a, low, mid-1, x);
    }
    else if(a[mid]<x){
        return ceilSearch(a, mid+1, high, x);
    }
    else{
        return mid;
    }
}

很简单，不是吗？我检查了很多输入，它确实有效，但我未能证明算法的正确性。有人可以尝试证明其正确性，或者您也可以提供此算法将失败的示例输入。谢谢。

Answer 1

代码中有一个传统错误。它使用 int mid = (low+high)/2;。如果数组非常大，则加法运算可能会溢出为负数，使 mid 为负数。

可以使用 int mid = (low+high)>>>1; 修复该错误，就像在 java.util.Arrays binarySearch 方法中所做的那样。 >>> 1 实际上是一个无符号除以 2。