1

我有一个序列，它首先单调递减，然后单调递增，f(1) > f(2) > f(3) > f(4) .... > f(k -1) > f(k) < f(k+1) < f(k+2) < ....... < f(n) 我希望能够找到元素 k 使得 f( k) 是序列和 O(lgn) 时间内的最小值，为了解决这个问题，我设计了以下基于二进制搜索的算法，有人可以告诉我该算法是否正确-：

用于决定二分搜索将在何处递归的属性-：

FindMin(F , lo , hi)

if(lo == hi) return F[lo];

int mid = lo + (hi-lo)/2;

// recurse to the left
if(F[mid] < F[mid+1]) return FindMin(F , lo , mid);
// recurse to the right
if(F[mid] < F[mid - 1]) return FindMin(F , mid , hi);

return F[mid];

有人可以确认我的算法是否正确吗？

4

3 回答 3

2

您当前的算法不正确，但您非常接近它。在这里，我将展示您的算法可能出错的地方。

考虑数组[3,2,1,2]。

假设你先打电话FindMin(F, 0, 3)

FindMin(F, 0, 3)
--mid = 1
--检查 F[1] 错误
--检查 F[1] 为真，调用 FindMin(F, 1, 3)
----中 = 2
----检查 F[2] 为真，调用 FindMin(F, 1, 2)
------中= 1
------检查 F[1] 否
------检查 F[1] 为真，调用 FindMin(F, 1, 2)
--------中= 1
--------检查 F[1] 假
--------检查 F[1] 为真，调用 FindMin(F, 1, 2)
...这将永远持续下去，直到内存不足

您可以对其进行一些更改以使其正确：

FindMin(F, lo, hi){
    if(lo==hi) return F[lo];
    int mid = lo + (hi-lo)/2 // Actually you can change this into (lo+hi)/2
    if(F[mid] > F[mid+1]) return FindMin(F, mid+1, hi) // Change the comparison and recursive call!
    if(F[mid] > F[mid-1]) return FindMin(F, lo, mid-1) // Change the comparison and recursive call!
    // If we reach here, that means F[mid-1] > F[mid] < F[mid+1]
    return F[mid]
}

尽管正如@Joni 所说，您需要处理边界情况。只检查F[mid+1]就可以了。我保证以下代码不会出现任何越界错误并且是正确的：

FindMin(F, lo, hi){
    if(lo==hi) return F[lo];                           // Line 1
    int mid = (lo+hi)/2                                // Line 2
    if(F[mid] > F[mid+1]) return FindMin(F, mid+1, hi) // Line 3
    else return FindMin(F, lo, mid)                    // Line 4
}

调用函数hi作为数组中的最后一个索引

第 1 行是基本情况。

第 2 行计算中间索引。注意mid < hi这里，sincemid == hi暗示lo == hi，这已经在第 1 行中介绍过。所以mid永远不要指向数组中的最后一个索引。所以检查是安全的F[mid+1]

第 3 行检查是否F[mid] > F[mid+1]，如果是，则F[mid]不能是答案，因为它比某个数字大，而且F[lo..mid-1]还会更大，所以答案必须在F[mid+1..hi]. 所以打电话FindMin(F, mid+1, hi)。请注意mid+1 > lo，所以范围mid+1..hi小于lo..hi。

第 4 行：如果我们到达这里，这意味着F[mid] < F[mid+1]. 所以答案可以在F[lo..mid]. 所以打电话FindMin(F, lo, mid)。请注意，因为mid < hi,FindMin(F, lo, mid)将不同于FindMin(F, lo, hi)。更具体地说，范围减小，如第 3 行中的情况。

结合第 3 行和第 4 行，每次调用FindMin都是以递减范围进行的，因此算法应该在一段时间后停止，这将在第 1 行中。

于 2013-09-27T06:31:40.083 回答
1

该算法的基本原理是正确的：用中间点来决定最小值是在右边还是在左边。

但这并不完全正确。看到这一点，想想什么时候mid是最小元素：因为你永远不能返回最小值；你进入一个无限递归。不过有一个简单的解决方法。F[mid] < F[mid+1]F[mid] < F[mid-1]

您必须记住的另一件事是，如果最小值是序列中的第一个或最后一个元素会发生什么：您无法计算F[mid-1]或F[mid+1]索引会超出范围。

于 2013-09-27T00:17:56.063 回答
1

假设mid = k。然后第一个条件为真，您在lo, mid. 在该部分中，元素按降序排列，它将遵循第二个条件，直到您在k-1, k. 但是mid = k-1 + (k-(k-1))/2 = k-1通过整数除法。这个不对。它将继续满足第二个条件——无限循环k-1, k。

看起来你的比较符号是倒退的。

于 2013-09-27T00:14:20.250 回答