algorithm - 未排序数组中的局部最小值

Question

假设我有一个 0<=i<=n-1 的数组 a[i]。我可以使用复杂度为 O(log n) 的算法找到 i 使得 1<=i<=n-2, a[i]<=a[i+1] 和 a[i]<=a[i -1]？也就是说，我能否在对数时间内找到一个局部极小值？

_{注意:我将问题(已更改多次)编辑为可以合理回答的问题。我删除了早期版本中出现的奇怪结束条件，因为这个版本更简单但不失通用性。}

Answer 1

首先，我们需要考虑如何定义局部最小值:

a[i] < a[i-1] and a[i] < a[i+1]

从这个条件来看，如果我们要在 X/Y 图上绘制数组(X=索引，Y = 值)，局部最小值将位于谷底。因此，要确保存在局部最小值，我们必须保证存在斜率符号的变化(从减少到增加)。

如果您知道范围的端点斜率行为，您就会知道范围内是否存在局部最小值。此外，您的数组必须具有从 a[0] 到 a[1] 递减斜率符号和从 a[n-1] 到 a[n] 递增斜率符号的行为，否则问题很简单。考虑:

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

我认为这应该足以激发您完成该方法。

请注意，扩展此方法仅适用于唯一值，例如全 1 的数组，除非您进行一些边缘情况检测，否则它不会有 O(log n) 运行时间。