YSMull
<-- algorithm



原题链接

题目描述

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设nums[-1] = nums[n] = -∞ 。
对于所有有效的 i 都有 nums[i] != nums[i + 1]

分析

使用二分模板:
原命题可转化为:

  1. 找到第一个比右边大的元素。
  2. 或者找到最后一个比左边大的元素。
    由于二分模板比较擅长找「第一个」,所以用第一种来实现。

实现

这里直接使用二分模板

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, nums)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
    // 找到第一个比右边大的
    public boolean check(int mid, int[] nums) {
        return nums[mid] > nums[mid + 1];
    }
}