4

从已排序的数组中查找数字 X 的 floor 和 ceil。例如

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

  • 如果 X=2，地板 = N/A，天花板 = 3
  • 如果 X=3，地板 = 3，天花板 = 3
  • 如果 X=4，地板 = 3，天花板 = 7
  • 如果 X=16, floor = 15, ceil = N/A

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

地板算法：

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

对于 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;
    }
}

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

4

4 回答 4

1

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

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

于 2013-09-13T02:05:26.647 回答
1

关于如何做证明的提示：

  1. 这些算法的正确性证明将遵循算法的递归结构；即使用结构归纳证明（查找）。

  2. 查看标准二分搜索的证明并弄清楚它是如何构造的。

  3. 如果您的代码中有错误，那么您应该找不到正确性证明；查看其他评论和其他答案！

于 2013-09-13T01:41:14.987 回答
0

由于您只修改了 condition if(low > high)，请注意这与普通二分搜索等效。理解二分搜索的证明，在这里确定正确性应该是微不足道的。

于 2013-09-13T01:44:20.073 回答
0

这是一个测试用例，它将破坏您的 ceilSearch 代码。

a={3, 7, 9, 11, 13}，x=10。

我在每个递归调用中列出低、高和中：

(0, 4, 2) -> a[2]=9 < x

(3, 4, 3) -> a[3]=11 > x

(3, 2, 2) -> 低 > 高，返回低 = 2。

正确答案是 3，而不是 2。

于 2018-01-29T13:22:05.713 回答