Find Peak Element

Problem Statement

A peak element in an array is an element that is strictly greater than its neighbors. Given an integer array nums, find any peak element and return its index. You may assume nums[-1] = nums[n] = -∞.

Example: nums = [1,2,3,1] → Output: 2 (nums[2] = 3 is a peak)

Approach 1: Linear Scan

Explanation: Traverse array and return first element greater than neighbors.

Time Complexity: O(n)

Space Complexity: O(1)

for i in 0..n-1:
    if (i==0 or nums[i] > nums[i-1]) and (i==n-1 or nums[i] > nums[i+1]):
        return i

Approach 2: Binary Search

Explanation: Compare middle element with neighbors; move to side with higher neighbor.

Time Complexity: O(log n)

Space Complexity: O(1)

low = 0
high = n-1
while low < high:
    mid = (low+high)//2
    if nums[mid] < nums[mid+1]:
        low = mid + 1
    else:
        high = mid
return low

Approach 3: Recursive Binary Search

Explanation: Recursively check mid and its neighbor to find peak.

Time Complexity: O(log n)

Space Complexity: O(log n) recursion stack

function findPeak(nums, low, high):
    if low == high:
        return low
    mid = (low+high)//2
    if nums[mid] < nums[mid+1]:
        return findPeak(nums, mid+1, high)
    else:
        return findPeak(nums, low, mid)