852.山脉数组的峰顶索引

描述

符合下列属性的数组 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

解题思路

常规的二分，思路还是比较简单的，正常设置left、mid、right，在中间的时候判断mid两边的元素：1.当nums[mid]<nums[mid-1]时，证明还没到峰值，right移动到mid左侧；2.当nums[mid]>nums[mid-1]时再判断是否nums[mid]>nums[mid+1]，若成立证明找到峰值，直接返回mid，若不成立则证明已经过了峰值，此时将reft移动到mid右边。这里要注意越界的问题，在计算完mid后判断一下是否已经到达最低点（0），若达到直接推出循环，同时返回right（因为在你计算mid后，mid已经移动到right左边，此时mid为0已经不能比较了，所以之前保留的right一定就是峰值）。这是常规做法，后面有更高效率的写法我再研究研究。

代码

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
	int left,mid,right;
    left=0;
     mid=10;
    right=arr.length-1;
    while(right>=left){
        mid=left+(right-left)/2;
        if(mid==0) return right;
        if(arr[mid]<arr[mid-1]){
            right=mid-1;
            }
        else if(arr[mid]>arr[mid-1]){
            if(arr[mid]>arr[mid+1])
                return mid;
            else left=mid+1;
            }
        }
        return right;
    }
}