问在数组中查找局部最小值

EN

如果不能保证数组元素是不同的，那么就不可能在O(log )时间内做到这一点。原因如下:假设您有一个数组，其中所有n>1的值都是相同的。在这种情况下，没有一个元素可以是局部最小值，因为没有一个元素小于它的邻居。但是，为了确定所有值都是相同的，您必须查看所有数组元素，这需要O(n)时间。如果您使用的时间少于O(n)，则不必查看所有数组元素。

另一方面，如果保证数组元素是不同的，则可以使用以下观察结果在O(log )时间内解决此问题：

1. 如果只有一个元素，则保证是局部最小值。
2. 如果有多个元素，请查看中间的元素。如果它是一个局部最小值，那么你就完成了。否则，它旁边的至少一个元素必须小于它。现在，想象一下，如果您从一个较小的元素开始，并逐渐向远离中间元素的方向移动到数组的一端，会发生什么情况。在每个步骤中，要么下一个元素比前一个元素小，要么它会更大。最终，要么以这种方式到达数组的末尾，要么达到局部最小值。请注意，这意味着您可以通过执行此操作，以找到局部最小值。然而，我们实际上并不打算这样做。相反，我们将使用在数组的这一半中存在局部最小值的事实作为丢弃一半数组的理由。在剩下的部分中，我们肯定会找到一个局部最小值。

因此，您可以构建以下递归算法：

1. 如果只有一个数组元素，则它是局部最小值。
2. 如果有两个数组元素，请检查每个元素。其中一个必须是局部minimum.
3. Otherwise，，查看数组的中间元素。如果它是局部最小值，则返回它。否则，必须至少有一个邻接值小于此值。在包含较小元素(但不是中间元素)的数组的一半中递归。

请注意，这具有递归关系

T(1)≤1

T(2)≤1

T(n)≤T(n / 2) +1

使用主定理，您可以根据需要证明此算法的运行时间为O(log )。

希望这能有所帮助！

还请注意，仅当数组的边小于相邻元素时，此算法才有效。

局部最小值的数量可以是n/2；您不能在O(log n)时间内将其全部枚举。

使用分而治之的算法。设m= n/2，检查Am的值。

案例1: Am−1 < Am那么数组的左半部分必须包含一个局部最小值，所以在左半部分上递归。我们可以用矛盾的方式来表示这一点:假设对于每个0≤i< m，Ai不是局部最小值，那么Am−1不是局部最小值，这意味着Am−2 < Am−1。类似地，Am−3 < Am−2。以这种方式继续，我们得到A

案例2: Am +1> Am那么数组的右半部分必须包含一个局部最小值，所以在右半部分上递归。这与情况1是对称的。

案例3: Am−1> Am和Am +1< Am那么Am是一个局部最小值，所以返回它。运行时间递归为T(n) = T(n/2) +Θ(1)，其结果是T(n) =Θ(log )。