一.题目描述

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

二.题目解析

题目给了我们一个山脉数组，山脉数组的值分布就如下面的样子：

然后我们只需要返回数组的峰值元素的下标即可。 

三.算法原理

1.暴力解法

因为题目明确说明，arr一定是一个山脉数组。所以它一定满足先递增后递减。所以暴力的解法就是遍历数组，找到一个数它既大于前面的数又大于后面的数即可。

时间复杂度：最坏情况下，峰值位于倒数第二个位置，所以时间复杂度为O(N)

空间复杂度：在遍历过程中，只涉及到了几个变量，所以空间复杂度为O(1)

2.二分查找算法

因为题目明确告诉我们这是一个山脉数组，所以它的二段性还是非常明显的。

如图所示，该数组有这样一种二段性。在上升阶段包含峰值，都满足当前位置大于前一个位置，在下降阶段，都满足当前位置小于前一个。

当mid落到左区间，该位置的值有可能就是峰值，所以我们不能让left跳过mid，所以left  = mid；

当mid落到有区间，该位置的值不可能是结果，所以我们直接让right跳过mid，所以right = mid-1. 

因为我们这里并没有单独处理等于的情况，所以这里不能用简单二分，而得用查找区间右端点的写法。

四.代码实现

//C++
//写法1：

class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int left = 1;
        int right = arr.size()-2;
        while(left<right)
        {
            int mid = left+(right-left+1)/2;
            if(arr[mid]>arr[mid-1])
            {
                left = mid;
            }
            else
            {
                right = mid-1;
            }
        }
        return left;
    }
};

//写法二：
class Solution 
{
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int ret = 0;

        int left = 0;
        int right = arr.size()-1;
        while(left<=right)
        {
            int mid = left+(right-left)/2;
            if(arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1])
            {
                left = mid;
            }
            else if(arr[mid] < arr[mid-1] && arr[mid] > arr[mid+1])
            {
                right = mid;
            }
            else
            {
                ret = mid;
                break;
            }
        }
        return ret;
    }
};

# python

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        left,right = 1,len(arr)-2
        while left<right:
            mid = left+(right-left+1)//2
            if arr[mid]>arr[mid-1]:
                left = mid
            else:
                right = mid - 1
        return left