Find Peak Element

1. Problem Description

A peak element is an element whose value is strictly greater than its adjacent values on both sides.

Given an integer array nums, find a peak element and return its index. The array may contain multiple peaks; in that case, returning the position of any peak is acceptable.

You may assume nums[-1] = nums[n] = -∞.

You must implement an algorithm with O(log n) time complexity.

2. Approach

1. Brute force
2. Binary search

3. Implementation

3.1. Brute Force

func findPeakElement(nums []int) int {
    for i, num := range nums {
        left := i-1
        right := i+1
        if ( left < 0 || nums[left] < num ) && (right >= len(nums) || nums[right] < num) {
            return i
        }
    }
    return -1
}

func max(a, b int) int {
    if a > b {return a}
    return b
}

3.2. Binary Search

func findPeakElement(nums []int) int {
    left := 0
    right := len(nums)-1
    /*
    Many people may still find this confusing after reading a diagram. The most important condition in this problem is that both outer boundaries are negative infinity. There may be many peaks in the array, or only one. If you draw the array, it can look like stock-price data with no obvious global pattern, so the key is deciding which direction to take from the midpoint. The problem only asks us to return one peak. Think of the midpoint as a point on a mountain: it may be the summit, on a downhill slope, or on an uphill slope. If it is the summit, binary search will eventually stop there. The important question is which direction to search when we do not know whether a peak lies to the left or right. Think of it as climbing a mountain. If you walk downhill, you might encounter another peak, but you might also keep descending until the boundary. If you walk uphill, even if the slope continues all the way to the boundary, the outside boundary is negative infinity, so a peak must exist along that direction. In short, binary-search toward the increasing direction: a peak is guaranteed there. Searching toward the decreasing direction may find a peak, but it may not.
    */
    for left < right {
        mid := left + (right-left) >> 1
        if nums[mid] < nums[mid+1] {
            left = mid+1
        }else {
            right=mid
        }
    }
    return left
}

4. References

• Illustrated Algorithm: 162. Find Peak Element - LeetCode