852. 山脉数组的峰顶索引

# 题目

## 852. 山脉数组的峰顶索引

[https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/](https://leetcode-cn.com/problems/peak-index-in-a-mountain-array/)

符合下列属性的数组 `arr` 称为 山脉数组 ：

- `arr.length >= 3`
- 存在`i`（`0 < i < arr.length - 1`）使得：
  
  - `arr[0] < arr[1] < ... arr[i-1] < arr[i]`
  - `arr[i] > arr[i+1] > ... > arr[arr.length - 1]`

给你由整数组成的山脉数组 `arr` ，返回任何满足 `arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]` 的下标 `i` 。

**示例 1：**

```
输入：arr = [0,1,0]
输出：1
```

**示例 2：**

```
输入：arr = [0,2,1,0]
输出：1
```

**示例 3：**

```
输入：arr = [0,10,5,2]
输出：1
```

**示例 4：**

```
输入：arr = [3,4,5,1]
输出：2
```

**示例 5：**

```
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
```

**提示：**

- `3 <= arr.length <= 104`
- `0 <= arr[i] <= 106`
- 题目数据保证 `arr` 是一个山脉数组

**进阶：** 很容易想到时间复杂度 `O(n)` 的解决方案，你可以设计一个 `O(log(n))` 的解决方案吗？

# 题解

## 思路

方法一：遍历数组，找到最大值

方法二：采用二分法，山峰一边是单调递增或递减，可以利用这用二分查找

## 代码

```javascript
/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    let left = 0;
    let right = arr.length - 1;
    let mid;
    while(left < right){
        mid = Math.floor(left + (right - left) / 2);
        if(arr[mid] > arr[mid + 1]){
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

```

## 参考

### 模板1：while(left<=right)

- 循环体内有3个分支
- 在循环体中返回目标索引

```
class Solution {
    public int peakIndexInMountainArray(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>nums[mid+1]&&nums[mid]>nums[mid-1]){
                return mid;
            }
            else if(nums[mid]>nums[mid+1]){
                right=mid-1;
            }
            else {
                left=mid+1;
            }
        }
        // 这里return什么都可以，因为对于此题来说，在循环体内一定会返回
        return -1;

}
}
```

### 模板2：while(left<right)

- 循环体内有2个分支
- 在循环体外返回目标索引，在循环体内缩减搜索区间

```
class Solution {
    public int peakIndexInMountainArray(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            // 缩减区间为[mid+1,right]
            if(nums[mid]<nums[mid+1]){
                left=mid+1;
            }
            // 缩减区间为[left,mid]
            else {
                right=mid;
            }
        }
        // left=right时退出循环，返回left或right是一样的
        return left;

}
}
```