Find Peak Element

A peak element is an element strictly greater than its neighbors. Given an array where nums[i] != nums[i+1], return the index of any peak.

Function signature

func FindPeakElement(nums []int) int

Inputs / outputs

• nums: array of integers.
• Return: an index of a peak element.

Example

nums = [1,2,3,1]
Output: 2  // nums[2] = 3 is a peak

Constraints

• 1 <= len(nums) <= 100_000
• nums[i] != nums[i+1]

Core idea (near-solution)

Use binary search on the slope. If nums[mid] < nums[mid+1], a peak must exist to the right; otherwise, a peak is at mid or to the left.

Invariant: there is always at least one peak in the current [lo, hi] range.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] < nums[mid+1], set lo = mid + 1.
   • Else set hi = mid.
3. Return lo.

Correctness sketch

• Invariant: there is always at least one peak in the current [lo, hi] range.
• The valid answer lies within the maintained [lo, hi] range.
• Each comparison discards half the range that cannot contain an answer.
• When the loop ends, the remaining boundary/index is correct.

Trace (hand walkthrough)

Example input:
nums = [1,2,3,1]
Output: 2  // nums[2] = 3 is a peak

Walk:
- lo=0, hi=3, mid=1: nums[1]=2 < nums[2]=3 -> lo=2
- mid=2: nums[2]=3 > nums[3]=1 -> peak at index 2

Pitfalls to avoid

• Accessing nums[mid+1] when mid is the last index (loop condition prevents this).
• Using linear scans when O(log n) is required.

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• The algorithm returns any valid peak, not necessarily the global maximum.