Medium

Find Peak Element

042

Return the index of any peak element. A peak is strictly greater than its neighbors.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    3,
    1
  ]
}

Output
2

FUNCTION SHAPE

nums: intArray→int

SOLUTION NOTE

Ternary search converted to binary search. Compare adjacent elements to determine which half contains a peak. Check nums[mid-1] <= nums[mid] creates monotone TTTFFF pattern.

Reveal reference solution +

pythonREFERENCE

def findPeakElement(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = ceil(left + (right - left) / 2)
        if nums[mid - 1] <= nums[mid]:
            left = mid
        else:
            right = mid - 1
    return left

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗