Solution Approach

We use the standard binary search template to find the first index where nums[mid] > nums[mid + 1] is true.

Initial Setup:

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]

This creates a pattern where the first true position is a peak element.

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

Example Walkthrough

Let's walk through the algorithm with the array nums = [1, 2, 1, 3, 5, 6, 4].

Setup:

• Array: [1, 2, 1, 3, 5, 6, 4]
• left = 0, right = 6
• first_true_index = -1
• Feasible condition: nums[mid] > nums[mid + 1]

Iteration 1:

• left = 0, right = 6
• mid = (0 + 6) // 2 = 3
• Check nums[3] = 3 > nums[4] = 5? No (not feasible, going up)
• Update: left = mid + 1 = 4

Iteration 2:

• left = 4, right = 6
• mid = (4 + 6) // 2 = 5
• Check nums[5] = 6 > nums[6] = 4? Yes (feasible, going down)
• Update: first_true_index = 5, right = mid - 1 = 4

Iteration 3:

• left = 4, right = 4
• mid = (4 + 4) // 2 = 4
• Check nums[4] = 5 > nums[5] = 6? No (not feasible, going up)
• Update: left = mid + 1 = 5

Loop ends (left > right)

Result:

• first_true_index = 5
• Return 5
• Verify: nums[5] = 6 is indeed a peak because 6 > 5 (left neighbor) and 6 > 4 (right neighbor)

Feasibility pattern for this array:

Index:      0      1      2      3      4      5      6
Value:      1      2      1      3      5      6      4
> next?:  false  true  false  false  false  true   true(boundary)

Note that the algorithm found index 5 as a peak, but index 1 (value 2) is also a valid peak. The template finds the leftmost peak after our first discovered feasible point.

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses binary search, which divides the search space in half with each iteration. In each iteration, we compare the middle element with its neighbor and decide which half of the array to continue searching. Since we reduce the problem size by half each time, the number of iterations is at most log₂(n), resulting in O(log n) time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space for the variables left, right, and mid, regardless of the input size. No additional data structures or recursive calls are used that would scale with the input size.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

The Pitfall: Using while left < right with right = mid instead of the standard template:

# INCORRECT variant
while left < right:
    mid = (left + right) // 2
    if nums[mid] > nums[mid + 1]:
        right = mid  # Wrong variant!
    else:
        left = mid + 1
return left

Correct Template Implementation:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if mid == n - 1 or nums[mid] > nums[mid + 1]:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Forgetting the Last Element Edge Case

The Pitfall: When mid == n - 1, there's no nums[mid + 1] to compare, causing an index out of bounds error.

Incorrect approach:

if nums[mid] > nums[mid + 1]:  # IndexError when mid == n - 1
    first_true_index = mid
    right = mid - 1

Correct approach:

# Handle last element separately (always feasible since nums[n] = -infinity)
if mid == n - 1 or nums[mid] > nums[mid + 1]:
    first_true_index = mid
    right = mid - 1

3. Integer Overflow in Mid Calculation

The Pitfall: Using (left + right) / 2 in languages with fixed integer sizes:

// INCORRECT - can overflow
int mid = (left + right) / 2;

Solution: Use overflow-safe calculation:

int mid = left + (right - left) / 2;

4. Comparing with Both Neighbors

The Pitfall: Checking both neighbors complicates the logic unnecessarily:

# Overly complex
if mid > 0 and mid < n - 1:
    if nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1]:
        return mid

Better approach: Just compare with mid + 1 - the binary search guarantees we find a peak by following the feasible condition.

5. Not Understanding Why the Template Works Here

The template works because the feasible pattern [false, ..., true, ...] maps to "going up, ..., going down, ...". The first true is where we transition from ascending to descending - which is exactly a peak.