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

21. 山峰数组的峰顶索引

题目链接

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

题目描述

题目示例

解法（二分查找）

算法思路

分析峰顶位置的数据特点，以及山峰两旁的数据特点：

• 峰顶数据特点：arr[i] > arr[i - 1] && arr[i] > arr[i + 1]
• 峰顶左边的数据特点：arr[i] > arr[i - 1] && arr[i] < arr[i + 1]，也就是呈上升趋势
• 峰顶右边数据的特点：arr[i] < arr[i - 1] && arr[i] > arr[i + 1]，也就是呈下降趋势

因此，我们可以分为以下两种情况：

• 如果 mid 位置的值小于 mid+1 位置的值，说明处于上升阶段，left = mid + 1
• 如果 mid 位置的值大于 mid+1 位置的值，说明处于下降阶段或到达峰顶，right = mid

C++ 算法代码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 区间划分：[ 小于峰值 ], [ 大于等于峰值 ](相当于查找左端点)
        int left = 0;
        int right = arr.size();
        while(left < right) {
            int mid = left + (right - left) / 2;
            // 对于偶数而言 mid 始终是在左边，所以判断条件是 arr[mid] < arr[mid + 1]
            if(arr[mid] < arr[mid + 1]) {
                left = mid + ;
            }  {
                right = mid;
            }
        }
         left;
    }
};