二分查找算法：山脉数组的峰顶索引与寻找峰值

2、因此，根据 mid 位置的信息，我们可以分为下面三种情况：

（1）如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；

（2）如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；

（3）如果 mid 位置就是山峰，直接返回结果。

1.2.2 算法实现

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1, 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;
    }
};

时间复杂度：O(logn)，空间复杂度：O(1)。

022 寻找峰值

题目描述：

2.1 算法思路：二分查找

2.1.1 算法思路

寻找二段性——

任取一个点 i，与下一个点 i + 1，会有如下两种情况：

（1）arr[i] > arr[i + 1]：此时【左侧区域】一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；

（2）arr[i] < arr[i + 1]：此时【右侧区域】一定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。

当我们找到【二段性】的时候，就可以尝试用【二分查找】算法来解决问题。

2.2 算法实现

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

时间复杂度：O(logn)，空间复杂度：O(1)。