题目

类型：二分查找
难度：中等
image.png

解题思路

对于可行的下标范围 [l,r]，随机一个下标 i；
如果下标 i 是峰值，返回 i 作为答案；
如果 nums[i]如果 nums[i]>nums[i+1]，那么抛弃 [i,r] 的范围，在剩余 [l,i−1] 的范围内继续随机选取下标。

代码

  1. class Solution {
  2.     public int findPeakElement(int[] nums) {
  3.         int n = nums.length;
  4.         int left = 0, right = n - 1, ans = -1;
  5.         while (left <= right) {
  6.             int mid = (left + right) / 2;
  7.             if (compare(nums, mid - 1, mid) < 0 && compare(nums, mid, mid + 1) > 0) {
  8.                 ans = mid;
  9.                 break;
  10.             }
  11.             if (compare(nums, mid, mid + 1) < 0) {
  12.                 left = mid + 1;
  13.             } else {
  14.                 right = mid - 1;
  15.             }
  16.         }
  17.         return ans;
  18.     }
  20.     // 辅助函数，输入下标 i，返回一个二元组 (0/1, nums[i])
  21.     // 方便处理 nums[-1] 以及 nums[n] 的边界情况
  22.     public int[] get(int[] nums, int idx) {
  23.         if (idx == -1 || idx == nums.length) {
  24.             return new int[]{0, 0};
  25.         }
  26.         return new int[]{1, nums[idx]};
  27.     }
  29.     public int compare(int[] nums, int idx1, int idx2) {
  30.         int[] num1 = get(nums, idx1);
  31.         int[] num2 = get(nums, idx2);
  32.         if (num1[0] != num2[0]) {
  33.             return num1[0] > num2[0] ? 1 : -1;
  34.         }
  35.         if (num1[1] == num2[1]) {
  36.             return 0;
  37.         }
  38.         return num1[1] > num2[1] ? 1 : -1;
  39.     }
  40. }