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

Question

假设我有一个数组a [i]为0 <= i <= n-1.我可以使用复杂度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 =值),局部最小值将在谷值.因此,为了确保存在局部最小值,我们必须保证斜率符号的变化(从减少到增加)存在.

如果您知道范围的端点斜率行为,则可以知道其中是否存在局部最小值.此外,您的数组必须具有从[0]到[1]的行为减少斜率符号,并且从[n-1]到[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)运行时.

Answer 2

我认为这是一个家庭作业问题，所以我回答得很恰当。如果您正在搜索局部最小值，则必须为您提供一个起始位置，因为您需要关于什么是“局部”的参考。如果左侧的元素小于该元素，则转到该元素并重试。否则，如果右侧的元素小于当前元素，则向右移动并重试。否则，当前元素是局部最小值。

编辑：在我阅读问题后添加了 O(log n) 时间的要求。我会考虑一个满足这个要求的解决方案。

另一个编辑：我认为这对于未排序数组的 O(log n) 时间要求是不可能的，因为没有办法将问题分成两半。另一方面，对于排序数组有一个简单的 O(1) 解决方案:)