⚡Flashcard Drill➔
NeetCode #273LC-162MediumBinary Search
← Back to All Problems

#273 · #162 · Find Peak Element(寻找峰值)

📌 Problem Statement & Constraints

A peak element is one strictly greater than its neighbours. Given an integer array nums, return the index of any peak. Assume nums[-1] = nums[n] = -infinity, so the boundaries can be peaks. The solution must run in O(log n). Constraints: 1 <= nums.length <= 1000, -2^31 <= nums[i] <= 2^31 - 1.

💡 Core Algorithmic Approaches

  1. Compare nums[mid] with nums[mid + 1]. If the sequence is rising, a peak must exist to the right; otherwise a peak is at or to the left of mid.
  2. This works because the virtual boundaries are -infinity, so the array cannot be increasing everywhere.
  3. The loop converges to a peak index in O(log n).
  4. Note that this does not require the array to be sorted -- only that a peak exists.

💻 Benchmark Python3 Implementation

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid + 1]:
                lo = mid + 1           # rising -> peak is to the right
            else:
                hi = mid               # falling -> peak is at or left of mid
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): the range halves each iteration.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Using hi = mid - 1: could skip the peak; use hi = mid.
  • Comparing with nums[mid - 1]: the right neighbour is the standard choice, since mid + 1 is always in range while mid - 1 may not be.
  • Assuming the array is sorted: it is not; the argument only needs the boundary conditions.
  • Trying to find the global maximum: any peak is acceptable, which is what makes the binary search valid.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems