You need to find a peak element in an array. A peak element is defined as an element that is strictly greater than both of its neighboring elements.

Given a 0-indexed integer array nums, your task is to find any peak element and return its index. If there are multiple peaks in the array, you can return the index of any one of them.

Important constraints:

• Elements at the boundaries have special conditions: you can imagine that nums[-1] = nums[n] = -∞ (negative infinity), where n is the length of the array
• This means the first element only needs to be greater than the second element to be a peak (since its left neighbor is considered as negative infinity)
• Similarly, the last element only needs to be greater than the second-to-last element to be a peak

Time complexity requirement: Your algorithm must run in O(log n) time, which suggests using a binary search approach rather than a linear scan.

Example scenarios:

• In an array like [1, 2, 3, 1], the element 3 at index 2 is a peak because 3 > 2 and 3 > 1
• In an array like [1, 2, 1, 3, 5, 6, 4], there are two peaks: index 1 (value 2) and index 5 (value 6). You can return either index

The key insight is that due to the boundary conditions and the definition of a peak, at least one peak element is guaranteed to exist in any non-empty array.

The key observation is that we need O(log n) time complexity, which immediately suggests binary search. But how can we apply binary search when the array isn't sorted?

We can define a feasible function: feasible(i) = nums[i] > nums[i + 1]. This determines whether index i is on a "downward slope" (going from current to next element).

Unlike a sorted array, this condition does not split the array into all false followed by all true. For [1, 2, 1, 3, 5, 6, 4] the values are false, true, false, false, false, true, true (the last index counts as true because nums[n] = -∞). Binary search still works, because of a different guarantee:

• If feasible(mid) is false, then nums[mid] < nums[mid + 1]. Walking right from mid + 1, the values must eventually stop rising (the array ends at -∞), so a peak exists somewhere in [mid + 1, right]. Moving left = mid + 1 keeps that peak in range, and it also means nums[left - 1] < nums[left] from then on.
• If feasible(mid) is true, then nums[mid] > nums[mid + 1]. Walking left from mid, the values must eventually stop rising in that direction (the array starts at -∞), so a peak exists in [left, mid]. We record mid and keep looking to its left.

When the loop ends, left sits on the last recorded index first_true_index. Its right side is lower because it was feasible, and its left side is lower because of the nums[left - 1] < nums[left] fact above (or because it is index 0). So that index is a peak, even though it may not be the leftmost peak.

For [1, 2, 3, 1], feasible is false, false, true, true, and the search returns index 2.

Because the last index always counts as feasible, first_true_index is always set.

Watch it run

Step through it below. Each midpoint's slope decides which way a peak must lie.

We use the standard binary search template with the condition nums[mid] > nums[mid + 1], keeping the last index where it held.

Initial Setup:

Copy
left, right = 0, len(nums) - 1
first_true_index = -1

Initialize the search boundaries and a variable to track the first position where the feasible condition is true.

Feasible Function: For any index mid, the feasible condition is: nums[mid] > nums[mid + 1]

The last index recorded by this search is always a peak (see the intuition above for why).

Binary Search Loop: Using while left <= right:

1. Calculate the middle index: mid = (left + right) // 2

2. Check if feasible (nums[mid] > nums[mid + 1]):

   • If true: This could be a peak (or there's a peak to the left). Record first_true_index = mid, then search left with right = mid - 1
   • If false: We're on an upward slope, so the peak must be to the right. Search right with left = mid + 1

Edge Case - Last Element: When mid == n - 1, there's no nums[mid + 1] to compare. However, since nums[n] = -∞ by definition, nums[n-1] > nums[n] is always true. We handle this by treating mid == n - 1 as feasible.

Return Result: After the loop, first_true_index holds the index of a peak element. Return first_true_index.

Time Complexity: O(log n) - We halve the search space in each iteration Space Complexity: O(1) - We only use a constant amount of extra space for the pointers