P175 查找数组的波峰

描述#

这个题目说的是，给你一个整数数组，数组中相邻的元素不相等，你要找到这个数组的波峰元素，然后返回它的下标。波峰元素指的是比左右相邻元素都要大的元素。

如果数组中包含多个波峰元素，则返回任意一个波峰元素的下标即可。你可以把数组左右边界之外的元素都看成负无穷大。

比如说，给你的数组是：
1, 2, 4, 1
这个数组中只有一个波峰元素 4，它大于左边的 2 和右边的 1。因此返回元素 4 的下标 2 即可。
再比如说，给你的数组是：
1, 2, 1, 2, 4
这个数组中有两个波峰元素，一个是 2，另一个为 4。波峰元素 2 大于它左右两边的 1，而波峰元素 4 大于左边的 2 和右边假想的负无穷大。因此返回这两个波峰元素任意的一个下标即可，也就是返回下标 1 或下标 4 都可以。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int findPeakElementSequentialSearch(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    for (int i = 0; i < nums.length-1; ++i)
      if (nums[i] > nums[i+1])
        return i;
    return nums.length-1;
  }

  // Time: O(log(n)), Space: O(1)
  public int findPeakElementBinarySearch(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    int low = 0, high = nums.length-1;
    while (low < high) {
      int mid = low + (high - low) / 2;
      int left = mid-1 >= 0 ? nums[mid-1] : Integer.MIN_VALUE;
      int right = mid+1 < nums.length ? nums[mid+1] : Integer.MIN_VALUE;
      if (nums[mid] > left && nums[mid] > right) return mid;
      else if (left > nums[mid]) high = mid - 1;
      else low = mid + 1;
    }
    return low;
  }

}