题解 | #寻找峰值# [P2]

对于i: 
如果i左右相邻的柱子都没i高，那么i就是peak, return i.
如果i右边相邻的柱子比i高，那么i的右侧一定存在peak, binarySearch right
如果i左边相邻的柱子比i高，那么i的左侧一定存在peak, binarySearch left
(如果左右都比i高,两遍都有peak, 随便挑一边search)

why？反证法.比如右边相邻的柱子比i高情况下，假设右边不存在peak, 那么右边必须单调递增。
但是最右边nums[n]=-INFINITE, 所以不可能单调递增 -> 假设不成立。

import java.util.*;

public class Solution {
    public int findPeakElement (int[] nums) {
      int l = 0, r = nums.length;
      // binary search nums[l, r)
      while (l < r) {
        int m= l + ((r-l) >> 1);
        boolean higherThanLeft = m-1 < 0 || nums[m] > nums[m-1];
        boolean higherThanRight = m+1 >= nums.length || nums[m] > nums[m+1];
        if (higherThanLeft && higherThanRight) 
          return m;  // found
        else if (higherThanRight) 
          r = m;  // search left
        else 
          l = m + 1;
      }
      return -1;  // shouldn't get here
    }
}