This is the question of the day for 2021-9-15 in LeetCode: “162. Looking for peaks”

1. Topic description

Peak elements are those whose values are strictly greater than their left and right neighbors.

Given an integer array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks.

You can assume that NUMs [-1] = nums[n] = -∞.

You have to implement order log n time to solve this problem.

Example 1:

Input: nums = [1,2,3,1] output: 2 explanation: 3 is the peak element, and your function should return its index 2.Copy the code

Example 2:

Input: nums = [1,2,1,3,5,6,4] Or return index 5 with a peak element of 6.Copy the code

2. Answer

  1. Returns an arbitrary peak index, using dichotomy
  2. Take the middle elementmidIf,nums[mid] > nums[mid + 1],midIn a little bit of decline, the peak is definitely atmidOn the left, at the same timemidIt could also be a peak, so discardmidOn the right, let’sright=mid
  3. ifnums[mid] <= nums[mid + 1].midIn the short ascent, the peak is definitely atmidOn the right,midIt can’t be a peak. Discard the element on the leftleft = mid + 1
  4. whenleft < right, the cycle continues
  5. Notice, I can’t write it hereleft <= right, such as(2, 1], will go on forever
const findPeakElement = nums= > {
    let [left, right] = [0, nums.length - 1];
    while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] > nums[mid + 1]) {
            / / drop
            right = mid;
        } else {
            / / up
            left = mid + 1; }}return left;
};
Copy the code

😄 has recently created an open source repository to summarize LeetCode’s daily problems. It is currently available in C++ and JavaScript, and you are welcome to provide other language versions!

🖥️ Warehouse address: “One of the Day series”