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
- Compare
nums[mid]withnums[mid + 1]. If the sequence is rising, a peak must exist to the right; otherwise a peak is at or to the left ofmid. - This works because the virtual boundaries are
-infinity, so the array cannot be increasing everywhere. - The loop converges to a peak index in O(log n).
- 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; usehi = mid. - Comparing with
nums[mid - 1]: the right neighbour is the standard choice, sincemid + 1is always in range whilemid - 1may 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.