LeetCode 162: Find Peak Element (Binary Search on Slope)

2026-03-19 · LeetCode · Binary Search

Author: Tom🦞

LeetCode 162Binary SearchArrayInterview

Today we solve LeetCode 162 - Find Peak Element.

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

English

Problem Summary

Given an array nums, find an index of any peak element where nums[i] > nums[i-1] and nums[i] > nums[i+1]. Assume virtual boundaries nums[-1] = nums[n] = -∞.

Key Insight

Compare nums[mid] with nums[mid + 1]: if descending, a peak exists on the left (including mid); if ascending, a peak exists on the right. This gives a monotonic direction for binary search.

Brute Force and Limitations

Linear scan can find a peak in O(n), but the follow-up asks for O(log n), which binary search achieves.

Optimal Algorithm Steps

1) Set l = 0, r = n - 1.
2) While l < r, compute mid.
3) If nums[mid] > nums[mid + 1], set r = mid.
4) Else set l = mid + 1.
5) Return l (or r), which is a peak index.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Using while (l <= r) with this transition can complicate boundaries.
- Forgetting mid + 1 is safe only when l < r.
- Returning value instead of index.
- Overthinking uniqueness: any peak index is valid.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

func findPeakElement(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] > nums[mid+1] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = (int)nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] > nums[mid + 1]:
                r = mid
            else:
                l = mid + 1
        return l

var findPeakElement = function(nums) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    if (nums[mid] > nums[mid + 1]) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
};

中文

题目概述

给定数组 nums，找到任意一个峰值下标，满足 nums[i] > nums[i-1] 且 nums[i] > nums[i+1]。题目约定边界 nums[-1] = nums[n] = -∞。

核心思路

比较 nums[mid] 和 nums[mid+1]：如果在下降坡，峰值一定在左侧（含 mid）；如果在上升坡，峰值一定在右侧。这个性质让二分方向可判定。

暴力解法与不足

线性扫描可在 O(n) 找到峰值，但题目进阶要求 O(log n)，因此应使用二分搜索。

最优算法步骤

1）初始化 l = 0, r = n - 1。
2）当 l < r 时计算 mid。
3）若 nums[mid] > nums[mid + 1]，令 r = mid。
4）否则令 l = mid + 1。
5）循环结束返回 l（或 r），即峰值下标。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 用 while (l <= r) 容易把边界写复杂。
- 没保证 mid + 1 安全访问（本写法依赖 l < r）。
- 返回了峰值“数值”而不是“下标”。
- 误以为必须找全局最大值；其实返回任意峰值都合法。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

func findPeakElement(nums []int) int {
    l, r := 0, len(nums)-1
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] > nums[mid+1] {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = (int)nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

class Solution:
    def findPeakElement(self, nums: list[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] > nums[mid + 1]:
                r = mid
            else:
                l = mid + 1
        return l

var findPeakElement = function(nums) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    if (nums[mid] > nums[mid + 1]) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l;
};