Find Peak

You are given a 0-indexed integer array, nums. Find a peak element, and return its index. If the array has more than one peak, you can return the index of any one of them.

Find Peak Element

Problem Statement

A peak element is an element that is strictly greater than the elements next to it.

You are given a 0-indexed integer array, nums. Find a peak element, and return its index. If the array has more than one peak, you can return the index of any one of them.

You can assume that nums[-1] = nums[n] = -∞. In other words, an element right at the edge of the array is always considered greater than an imaginary neighbor outside the array.

You must write an algorithm that runs in O(log n) time.

Examples

Example 1

Input: nums = [1, 2, 3, 1]

Output: 2

Explanation: 3 is a peak element, so the function should return index 2.

Example 2

Input: nums = [1, 2, 1, 3, 5, 6, 4]

Output: 5

Explanation: The function can return either index 1 (where the peak element is 2) or index 5 (where the peak element is 6).

Constraints

• 1 ≤ nums.length ≤ 1000
• −2³¹ ≤ nums[i] ≤ 2³¹ − 1
• nums[i] != nums[i + 1] for all valid i (no two neighboring elements are equal).

Solution

We use the Type 2 binary search method (low < high), since this problem needs us to eliminate half of the array at each step, based on a simple comparison.

Steps

• At each mid point, we compare nums[mid] with its next neighbor, nums[mid + 1]:
  • If nums[mid] is smaller than nums[mid + 1], it means the values are still going up. So a peak must exist somewhere to the right. We move start forward, to mid + 1.
  • Otherwise, nums[mid] is greater than or equal to its next neighbor, meaning we're already past an increasing slope, or we're right at a peak. In this case, the peak could be mid itself, or somewhere to the left. So we move end back to mid (not mid - 1, since mid could still be the answer).
• We repeat this until start and end become equal. At that point, we've found the index of a peak element.

Code

var findPeakElement = function(nums) {

    let start = 0;
    let end = nums.length - 1;

    while (start < end) {
        let mid = start + Math.floor((end - start) / 2);

        if (nums[mid] < nums[mid + 1]) {
            start = mid + 1;
        } else {
            end = mid;
        }
    }
    return start;
};