c - c中数组中的峰值元素

Question

我得到了一个整数数组。我必须在其中找到一个峰值元素。如果一个数组元素不小于它的邻居，那么它就是峰值。对于角落元素，只考虑一个邻居。

例如:

对于输入数组{10, 20, 15, 2, 23, 90, 67}有两个峰值元素:20 和 90。我需要返回任何一个峰值元素。

我尝试的解决方案是对阵列进行线性扫描，我发现了一个峰值元素。这种方法的最坏情况时间复杂度为 O(n)。

我们能否找到比 O(n) 更好的最坏时间复杂度的峰值元素？

Answer 1

是的，您可以使用类似于二进制搜索的想法在 O(log n) 中完成。指向 vector 的中间并检查它的邻居。如果它大于其邻居的两者，则返回该元素，它是一个峰值。如果右边的元素更大，则递归地在数组的右边找到峰值。如果左边的元素更大，则递归地在数组的左边找到峰值。