arrays - 数组中的峰元素

Question

所以我试图解决以下问题:

Given an array of integers. Find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements, we need to consider only one neighbor. For example, for input array {5, 10, 20, 15}, 20 is the only peak element. For input array {10, 20, 15, 2, 23, 90, 67}, there are two peak elements: 20 and 90. Note that we need to return any one peak element.

来自以下链接:http://www.geeksforgeeks.org/find-a-peak-in-a-given-array/

有一次他们说

If the middle element is smaller than the its left neighbor, then there is always a peak in left half.

我在这一点上感到困惑，我们如何确定左半部分会有一个峰值元素？我可以从中得出的结论是，至少有 1 个元素肯定比它的右邻居大(即 a[m-1])，所以机会它可能是峰值元素)我有在 stackoverflow 和其他网站上进行了研究，但找不到对上述结论的良好解释

感谢您的帮助!

Answer 1

假设您站在一个低于其左侧邻居的中间元素上:

            element
                         you
                       element

你向左看。它看起来像一座小山。

假设你爬上那座山。你看到了什么？那么，存在三种可能性:

1.
  element
              you
            element

                       element

2.
              you
  element   element

                       element

3.
              you
            element

  element              element

在情况 2 和 3 中，万岁!你找到了一个高峰。在情况 1 中，您继续攀登。最终，要么你看到一个不比你高的元素，要么你撞到了左边的墙。无论哪种情况，您都找到了峰值。