在一个数组中找到2个峰

Question

我有一个数组，其顺序类似于

增加，减少，增加，减少。

我想知道什么是两个局部最大元素在增加行为的末尾。我知道我可以在O（n）时间找到他们，我想知道是否有可能在O（log n）时间或O（n）时间以上找到它。

Answer 1

如果你不知道你的数据遵循特定的模式 - 增加后减小再增大后减小的趋势 - 那么你可以做的最好的是O（n），因为你将要研究每一个项目在数组中确定哪两个最高点是。

如果你知道它肯定确实遵循这种模式，那么我最好的猜测是二进制搜索的改编，肚里大致为：

• 挑数据集的中间点，选中“渐变“ - 两个连续值之间的差异。
• 利用这个来划分的数据在半套，再次检查你的两个新的空间的中间点;你希望以这种方式继续细分，直到你发现你有足够的数据点，然后按顺序排列。在这两个点之间是其中一个低谷，在第一个低点的左边，最后一个点的右边是你要找的高峰。
• 执行二进制搜索这两个空间的找到实际的峰 - 再次，每次找到梯度检查两个值，而不是只抽样单值，所以你可以告诉保持其方向搜索

。

没有做数学，我现成的，顶级的我头的猜测是，这个算法是O（2log（n））的充其量为O（n），在最坏的情况。这当然会是非常罕见的，它需要你只要搜索整个数据集，我觉得你需要一个平凡的小数据集比天真的搜索需要更长的时间。