162. Find Peak Element

Source link: https://leetcode.com/problems/find-peak-element/

Design

The basic idea of this problem is to apply the binary search approach, and find out which side of the middle point is the peak element at.

  1. Find out the middle point mid1 and record its next element as mid2.
  2. See if nums[mid1] > nums[mid2], which means that the trend of the array is going down and the peak element is at the left side of the middle point. So we drop the right half of the array. Otherwise, drop the right side.

Implementation

class Solution {
  public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid1 = left + (right - left) / 2;
      int mid2 = mid1 + 1;

      if (nums[mid1] > nums[mid2]) {
        right = mid1;
      } else {
        left = mid2;
      }
    }

    return left;
  }
}

Complexity Analysis

Time: $O(logn)$

Space: $O(1)$