山脉数组的峰顶索引

一、题目描述

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?。

你必须设计并实现时间复杂度为?O(log(n))?的解决方案。

二、题目解析

本题要求算法的时间复杂度是O(logN)，明显提示需要用到二分算法，但这道题数组的顺序是无序的，我们怎么使用二分去解决呢？

判断使用二分的条件并不是是否有序，而是看是否有二段性！！！

本题可以将区间划分为两个位置，第一段是逐步递增，第二段是逐步递减，而我们要查找的那个值就是在就是在递增区间的最后一个位置，因此我们可以根据条件判断当前位置的值和当前位置的前一个值进行大小比较，更具结果可以判断在哪个区间，这样可以进行二分！

三、原码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        //有二段性，使用二分
        int left = 1;
        int right = arr.size()-2;
        int mid = 0;
        while(left < right)
        {
            mid = left + (right-left + 1)/2;
            if(arr[mid] > arr[mid-1])
                left = mid;
            else
                right = mid-1;
        }
        return right;
    }
};

?