Binary Search - DSA: Find Peak Element

A comprehensive exploration of the Find Peak Element problem. This note covers the transition from a naive linear search to an optimal logarithmic Binary Search approach, complete with visualizations, edge cases, and handling arrays with multiple peaks.

1. Problem Statement & Definition of a Peak

A peak element is defined as an element at an index i that is strictly greater than both its left and right neighbors:

Important Rule: The comparison requires strictly greater (>), not greater than or equal to (>=). Consecutive elements in the array are guaranteed to be distinct (no flat plateaus).

Boundary Conditions (-inf Assumption)

If an element is located at the extreme boundaries (index 0 or index n-1), the problem statement assumes virtual $-\infty$ (minus infinity) elements beyond the array bounds:

• To the left of index 0, assume an element of value $-\infty$.
• To the right of index n-1, assume an element of value $-\infty$.

This guarantees that every array, regardless of its values, contains at least one peak element.

2. Real-World Graphical Mental Model

To understand how binary search applies to peak finding, imagine tracing the elevation of a terrain (or stock price chart) that goes up and down.

• Single Peak Terrain: The elevation rises linearly or non-linearly to a peak, then drops down.
• Multiple Peak Terrain: The elevation rises and falls multiple times across the array (Up -> Down -> Up -> Down).

3. Naive Approach: Linear Scan

The most intuitive way to solve this problem is to inspect every single element sequentially from left to right.

Algorithm Walkthrough

1. Start at index i = 0.
2. Check if arr[i] is greater than its left neighbor (if i > 0) and right neighbor (if i < n - 1).
3. If the condition is met, return index i.
4. Otherwise, increment i and repeat.

Complexity Analysis

• Time Complexity: $O(n)$ because we traverse the array elements one by one.
• Space Complexity: $O(1)$ auxiliary space.

An interviewer will expect an optimization beyond $O(n)$, prompting us to look for a logarithmic $O(\log n)$ solution using Binary Search.

4. Why Binary Search Works Here

Even though the array is not fully sorted, it exhibits local sorting tendencies (sub-portions are either increasing or decreasing). We can leverage binary search because:

1. We are searching for a specific condition across a search space.
2. At any mid-point, we can determine whether the peak lies to our left or to our right by observing the slope.

5. Step-by-Step Evolution: Single-Peak Array

Let us assume for a moment that the array contains only one peak.

The Three Midpoint Scenarios

When we compute mid = low + (high - low) / 2, three scenarios can occur:

1. mid is the Peak: $\text{arr}[mid]$ is greater than both $\text{arr}[mid-1]$ and $\text{arr}[mid+1]$. We have found our answer.
2. mid is on an Increasing Slope: $\text{arr}[mid] > \text{arr}[mid-1]$ (or $\text{arr}[mid] < \text{arr}[mid+1]$). This means the curve is going upward towards the right. Therefore, the peak must lie on the right half. We discard the left half (low = mid + 1).
3. mid is on a Decreasing Slope: $\text{arr}[mid] < \text{arr}[mid-1]$. This means the curve is going downward towards the right. Therefore, the peak must lie on the left half. We discard the right half (high = mid - 1).

6. Handling Boundary Overflow Risks

If we run standard binary search where low = 0 and high = n - 1, evaluating mid - 1 when mid = 0 causes an index underflow (arr[-1]), and evaluating mid + 1 when mid = n - 1 causes an index overflow (arr[n]).

The Clean Solution: Manual Boundary Checks

Instead of writing complex conditional guards inside the binary search loop, we handle the first and last elements manually before starting binary search:

By trimming our search space to low = 1 and high = n - 2, mid will never land on 0 or n - 1, completely eliminating index out-of-bound errors.

7. Extending to Multiple Peaks

What happens if the array contains multiple peaks (e.g., [1, 2, 1, 3, 5, 6, 4])?

Even with multiple peaks, the binary search logic holds true:

• If mid is on an increasing slope, discarding the left half is safe because at least one peak is guaranteed to exist in the right half.
• If mid is on a decreasing slope, discarding the right half is safe because at least one peak is guaranteed to exist in the left half.

The Single Adjustment for Multiple Peaks

When multiple peaks exist, a midpoint might land in a "valley" (where it is smaller than both neighbors).

• In a single-peak array, this never happens.
• In a multi-peak array, if mid falls into a valley, we can simply treat it as part of the decreasing slope branch (e.g., direct the search to the left or right, or fall into a default else block). Eliminating either half will still successfully lead us to one valid peak.

8. Complete Code Implementation (Java)

Here is the production-grade, optimized implementation handling single peaks, multiple peaks, and edge cases cleanly:

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
        
        // Edge Case 1: If array has only 1 element
        if (n == 1) return 0;
        
        // Edge Case 2: Check if the first element is a peak
        if (nums[0] > nums[1]) return 0;
        
        // Edge Case 3: Check if the last element is a peak
        if (nums[n - 1] > nums[n - 2]) return n - 1;
        
        // Trim search space to avoid boundary checks inside binary search
        int low = 1, high = n - 2;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // Check if mid is the peak element
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            }
            
            // If we are on the increasing slope, peak lies on the right
            else if (nums[mid] > nums[mid - 1]) {
                low = mid + 1;
            }
            
            // If we are on the decreasing slope (or in a valley), peak lies on the left
            else {
                high = mid - 1;
            }
        }
        
        // Dummy return statement required by compiler (never reached due to problem constraints)
        return -1;
    }
}

Summary and Key Takeaways

• Problem Definition: A peak element is strictly greater than its adjacent neighbors, with virtual $-\infty$ values assumed beyond array boundaries.
• Guaranteed Existence: Because of the infinite boundary assumption, every array is guaranteed to contain at least one peak.
• Brute Force vs. Optimal: Linear scan runs in $O(n)$ time, while Binary Search optimizes the search to $O(\log n)$ time.
• Slope Visualization: Binary search decides whether to move left or right based on whether mid is resting on an increasing or decreasing slope.
• Boundary Management: Manually checking index 0 and index n-1 upfront prevents messy index-overflow checks inside the core binary search loop.
• Multiple Peaks Resilience: Discarding half the search space on a multi-peak array still guarantees finding at least one valid peak because remaining sub-segments retain peak properties.
• Space Complexity: The algorithm operates in $O(1)$ auxiliary space.