162.Find Peak Element

Posted on | In

Solution 1: accepted

Binary search.

Since nums[-1] and num[n] are negative infinite, there must be a peak in the middle. Consider four conditions that mid may have, we can narrow the scope by half each time.

  1. mid - 1 < mid > mid + 1: mid is the peak.
  2. mid - 1 < mid < mid + 1: mid < mid + 1 [peak] len - 1 > -infinite, there must be a peak on right side.
  3. mid - 1 > mid > mid + 1: -infinite < 1 [peak] mid - 1 > mid, there must be a peak on left side.
  4. mid - 1 > mid < mid + 1: mid is a pit, either side has a peak. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findPeakElement(int[] nums) {
    int len = nums.length;
    if (len == 0) return -1;
    if (len == 1 || nums[0] > nums[1]) return 0;
    if (nums[len - 1] > nums[len - 2]) return len - 1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
            return mid;
        else if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
            hi = mid;
        else if (nums[mid] < nums[mid - 1] && nums[mid] > nums[mid + 1])
            hi = mid;
        else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1])
            lo = mid;
    }
    return lo + 1;
}