Find Peak Element medium

Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may assume that nums[-1] = nums[n] = -∞.

Constraints:

• 1 <= nums.length <= 1000
• -2³¹ <= nums[i] <= 2³¹ - 1
• nums[i] != nums[i+1] for all valid i

Example 1:

Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4] Output: 5 Explanation: 6 is a peak element and your function should return the index number 5.

Steps:

The problem can be efficiently solved using binary search. The core idea is that if nums[mid] < nums[mid + 1], then a peak must exist in the right half (mid + 1 to n-1). Conversely, if nums[mid] < nums[mid - 1], a peak must exist in the left half (0 to mid - 1). Otherwise, nums[mid] is a peak itself.

Explanation:

The algorithm uses binary search to efficiently find a peak element. We initialize left and right pointers to the beginning and end of the array, respectively. In each iteration:

1. Calculate the middle index: mid = (left + right) // 2.
2. Check the neighbors: Compare nums[mid] with its neighbors nums[mid - 1] and nums[mid + 1]. Handle boundary cases (when mid is 0 or n-1) carefully.
3. Adjust the search space: If nums[mid] < nums[mid + 1], the peak lies in the right half; otherwise, if nums[mid] < nums[mid - 1], the peak lies in the left half. If neither condition is true, nums[mid] is a peak.
4. Repeat: Continue the binary search until left and right converge.

Code:

def findPeakElement(nums):
    """
    Finds a peak element in the given array using binary search.

    Args:
        nums: A list of integers.

    Returns:
        The index of a peak element.
    """
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            right = mid
    return left

Complexity:

• Time Complexity: O(log n), due to the binary search.
• Space Complexity: O(1), as the algorithm uses a constant amount of extra space.