Find Peak Element in C++

Find Peak Element in C++ is one of the most intellectually rewarding and frequently tested binary search problems in technical interviews at top-tier engineering organizations such as Google, Meta, Apple, and Amazon. A Peak Element is defined as an element that is strictly greater than its immediate neighbors: nums[i] > nums[i - 1] and nums[i] > nums[i + 1]. With boundary conditions defined as nums[-1] = nums[n] = -∞, the challenge is to find the index of any peak element in guaranteed O(log N) time complexity. In this comprehensive masterclass, we will navigate the complete algorithmic evolution: starting with an intuitive Brute Force linear scan, advancing through Recursive Divide and Conquer, and ultimately engineering the Optimal Iterative Gradient Binary Search. We will also explore mathematical existence proofs, terrain slope topologies, CPU branch prediction profiling, and a 10,000,000-element performance benchmark lab using clear code, outputs, and “Try it yourself” challenges after every section.

🔹 What is a Peak Element? Mathematical Invariants & Terrain Model

To build an intuitive mental model, imagine walking along a mountainous hiking trail. The elevation at each step i is given by nums[i]. Because nums[-1] = nums[n] = -∞, you start at the bottom of a canyon, walk through mountain ridges, and finish at the bottom of another canyon.

Array: [1, 2, 1, 3, 5, 6, 4]
Index:  0  1  2  3  4  5  6

Elevation Profile:
  7 ┤                     ╭── [6] (Peak 2 at index 5)
  5 ┤                  ╭──╯   │
  3 ┤       ╭── [2] (Peak 1)  │ ╭── [3]
  1 ┤ ╭─────╯   │  │          │ │   │   ╭── [4]
    └─┴─────────┴──┴──────────┴─┴───┴───┴───────
     -∞         0  1  2  3  4  5    6  +∞

• Peak Definition: Index i is a peak if nums[i] > nums[i - 1] and nums[i] > nums[i + 1].
• Boundary Conditions:
  • For index 0: Only needs to satisfy nums[0] > nums[1] (since nums[-1] = -∞).
  • For index N – 1: Only needs to satisfy nums[N - 1] > nums[N - 2] (since nums[N] = -∞).
• Problem Invariant: Adjacent elements are strictly non-equal (nums[i] != nums[i + 1] for all valid i). This guarantees that every step is either strictly ascending or strictly descending, no flat horizontal plateaus exist.
• Guarantee of Peak Existence: Because the array starts above -∞ and ends below -∞, by the Discrete Intermediate Value Theorem, there is guaranteed to be at least one peak element in EVERY valid array!

Try it yourself

• What is the peak in a strictly increasing array like [1, 2, 3, 4, 5]? (Hint: Check the boundary index N – 1).
• What is the peak in a strictly decreasing array like [5, 4, 3, 2, 1]? (Hint: Check index 0).

🔹 Approach 1: Brute Force (Linear Scan)

Intuition & Reasoning: The most straightforward method is to inspect elements sequentially from left to right. Since nums[-1] = -∞, the first element nums[0] is already greater than its left neighbor. As we scan forward, the moment we encounter an element that is greater than its right neighbor (nums[i] > nums[i + 1]), that element must be a peak!

Why? Because if we reached index i without stopping earlier, it means nums[i - 1] < nums[i] was true for all prior steps. Therefore, nums[i] is strictly greater than both nums[i - 1] and nums[i + 1].

#include <iostream>
#include <vector>

using namespace std;

// Brute Force: Linear Scan
int find_peak_linear(const vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    
    // Scan up to the second-to-last element
    for (int i = 0; i < n - 1; ++i) {
        if (nums[i] > nums[i + 1]) {
            return i; // First downward slope -> nums[i] is a peak!
        }
    }
    
    // If we reach the end, the last element must be the peak
    return n - 1;
}

int main() {
    vector<int> nums1 = {1, 2, 3, 1};
    vector<int> nums2 = {1, 2, 1, 3, 5, 6, 4};

    cout << "--- Brute Force Linear Scan ---\n";
    cout << "Peak index in [1, 2, 3, 1]:           " << find_peak_linear(nums1) << " (Value: " << nums1[find_peak_linear(nums1)] << ")\n";
    cout << "Peak index in [1, 2, 1, 3, 5, 6, 4]: " << find_peak_linear(nums2) << " (Value: " << nums2[find_peak_linear(nums2)] << ")\n";
    return 0;
}

Output

--- Brute Force Linear Scan ---
Peak index in [1, 2, 3, 1]:           2 (Value: 3)
Peak index in [1, 2, 1, 3, 5, 6, 4]: 1 (Value: 2)

Takeaway: The linear scan correctly identifies the first peak element in O(N) time. For [1, 2, 1, 3, 5, 6, 4], it returns index 1 (value 2), which is indeed a valid local peak.

Step by Step Dry Run (Array = [1, 2, 1, 3, 5, 6, 4]):

┌───────┬───────────┬──────────────┬────────────────┬───────────────────────────────┐
│ Step  │ Index (i) │ nums[i]      │ nums[i + 1]    │ Condition (nums[i] > nums[i+1])│
├───────┼───────────┼──────────────┼────────────────┼───────────────────────────────┤
│ 1     │ 0         │ 1            │ 2              │ 1 > 2 (False) -> Continue     │
│ 2     │ 1         │ 2            │ 1              │ 2 > 1 (True)  -> Return Index 1│
└───────┴───────────┴──────────────┴────────────────┴───────────────────────────────┘
Peak found at Index 1 (Value = 2).

Complexity Analysis & The Bottleneck:

• Time Complexity (TC): O(N): In the worst case (a strictly increasing array such as [1, 2, 3, 4, 5, 6, 7]), the algorithm must iterate through all N elements before returning N – 1.
• Space Complexity (SC): O(1): Requires only a single integer loop counter.
• The Bottleneck: When N = 10,000,000, iterating sequentially wastes CPU cycles. Because we are allowed to return any peak, we do not need to find the first peak, we only need to follow an ascending gradient to find some peak in logarithmic time.

Try it yourself

• Trace what happens if the input array contains only a single element [42]. Why does find_peak_linear immediately return 0?
• If an array has 5 separate peaks, how many of them will Linear Search ever discover?

🔹 Approach 2: Better (Recursive Divide and Conquer)

Optimization Intuition: Instead of stepping linearly, we can inspect the midpoint mid = (low + high) / 2. By comparing nums[mid] with its right neighbor nums[mid + 1], we can determine the local slope:

• Ascending Slope (nums[mid] < nums[mid + 1]): The terrain is rising towards the right. Since nums[n] = -∞, the elevation must eventually peak and drop. Therefore, at least one peak is guaranteed to exist in the right half [mid + 1, high].
• Descending Slope (nums[mid] > nums[mid + 1]): The terrain is falling towards the right. A peak must exist at mid itself or in the left half [low, mid].

#include <iostream>
#include <vector>

using namespace std;

// Recursive Helper
int search_peak_recursive(const vector<int>& nums, int low, int high) {
    if (low == high) {
        return low; // Base case: Search space reduced to a single peak index
    }

    int mid = low + (high - low) / 2;

    if (nums[mid] < nums[mid + 1]) {
        // Upward slope: Peak must exist to the right of mid
        return search_peak_recursive(nums, mid + 1, high);
    } else {
        // Downward slope: Peak is at mid or to the left of mid
        return search_peak_recursive(nums, low, mid);
    }
}

int find_peak_divide_and_conquer(const vector<int>& nums) {
    return search_peak_recursive(nums, 0, static_cast<int>(nums.size()) - 1);
}

int main() {
    vector<int> nums = {1, 2, 1, 3, 5, 6, 4};

    cout << "--- Recursive Divide and Conquer ---\n";
    int peak_idx = find_peak_divide_and_conquer(nums);
    cout << "Peak index: " << peak_idx << " (Value: " << nums[peak_idx] << ")\n";
    return 0;
}

Output

--- Recursive Divide and Conquer ---
Peak index: 5 (Value: 6)

Takeaway: The recursive divide and conquer approach reduces time complexity to O(log N), successfully locating peak index 5 (value 6) in just 3 recursive calls.

Complexity Analysis & Limitations:

• Time Complexity (TC): O(log N): On each recursive call, the search space is divided by 2. The recurrence relation is T(N) = T(N / 2) + O(1), which evaluates by Master Theorem to O(log N).
• Space Complexity (SC): O(log N): Each recursive step pushes an activation frame onto the program call stack, requiring O(log N) stack space.
• The Inefficiency: While logarithmic, recursive calls incur CPU function call overhead (saving registers, moving the stack pointer, jumping instruction addresses). In production low-latency code, we can rewrite this as a flat, iterative O(1) auxiliary memory loop.

Try it yourself

• Why does the recursive base case terminate at low == high instead of low > high?
• Trace the call stack depth when running recursive divide and conquer on an array of size 1,048,576 (2²⁰ elements).

🔹 Approach 3: Optimal (Iterative Gradient Binary Search)

The Core Mathematical Invariant (Gradient Climbing): We can conceptualize this algorithm as a discrete 1D gradient ascent. At any arbitrary midpoint index mid, we inspect the gradient vector between nums[mid] and nums[mid + 1]:

Case 1: Ascending Slope (nums[mid] < nums[mid + 1])
Elevation is RISING to the right.
Since nums[N] = -∞, the elevation MUST eventually crest into a peak!
Action: low = mid + 1; (Discard left half completely)

        / (nums[mid+1])
       /
      / (nums[mid])
─────┴───────────────────────
   [low ... mid]  [mid+1 ... high]  -> Search RIGHT!

Case 2: Descending Slope (nums[mid] > nums[mid + 1])
Elevation is FALLING to the right.
A peak MUST exist at mid itself or somewhere to the left of mid!
Action: high = mid; (Keep mid in search space!)

      \ (nums[mid])
       \
        \ (nums[mid+1])
─────┴───────────────────────
   [low ... mid]  [mid+1 ... high]  -> Search LEFT!

Because we set high = mid (rather than mid - 1) when on a downward slope, we never accidentally discard mid when mid is the actual peak. When low == high, the search interval has converged to a single guaranteed peak index in O(log N) time and O(1) stack memory!

#include <iostream>
#include <vector>

using namespace std;

// Optimal: Iterative Gradient Binary Search
int find_peak_optimal(const vector<int>& nums) {
    int low = 0;
    int high = static_cast<int>(nums.size()) - 1;

    // Search space converges when low == high
    while (low < high) {
        // Prevent signed integer overflow
        int mid = low + (high - low) / 2;

        if (nums[mid] < nums[mid + 1]) {
            // Ascending slope: Peak must lie strictly to the right of mid
            low = mid + 1;
        } else {
            // Descending slope: Peak is at mid or to the left of mid
            high = mid;
        }
    }

    // low == high pointing directly to a valid peak element
    return low;
}

int main() {
    vector<int> nums1 = {1, 2, 3, 1};
    vector<int> nums2 = {1, 2, 1, 3, 5, 6, 4};
    vector<int> nums3 = {1};
    vector<int> nums4 = {1, 2};
    vector<int> nums5 = {2, 1};

    cout << "--- Optimal Iterative Binary Search ---\n";
    cout << "Peak in [1, 2, 3, 1]:           Index " << find_peak_optimal(nums1) << " (Value: " << nums1[find_peak_optimal(nums1)] << ")\n";
    cout << "Peak in [1, 2, 1, 3, 5, 6, 4]: Index " << find_peak_optimal(nums2) << " (Value: " << nums2[find_peak_optimal(nums2)] << ")\n";
    cout << "Peak in [1]:                   Index " << find_peak_optimal(nums3) << " (Value: " << nums3[find_peak_optimal(nums3)] << ")\n";
    cout << "Peak in [1, 2]:                Index " << find_peak_optimal(nums4) << " (Value: " << nums4[find_peak_optimal(nums4)] << ")\n";
    cout << "Peak in [2, 1]:                Index " << find_peak_optimal(nums5) << " (Value: " << nums5[find_peak_optimal(nums5)] << ")\n";
    return 0;
}

Output

--- Optimal Iterative Binary Search ---
Peak in [1, 2, 3, 1]:           Index 2 (Value: 3)
Peak in [1, 2, 1, 3, 5, 6, 4]: Index 5 (Value: 6)
Peak in [1]:                   Index 0 (Value: 1)
Peak in [1, 2]:                Index 1 (Value: 2)
Peak in [2, 1]:                Index 0 (Value: 2)

Takeaway: The iterative binary search handles single-element arrays, monotonic arrays, and multi-peak terrain with uniform elegance and zero boundary bugs.

Step by Step State Transition Trace (Array = [1, 2, 1, 3, 5, 6, 4]):

┌──────┬─────┬──────┬─────┬───────────┬───────────────┬──────────────────────────┬────────────┐
│ Pass │ low │ high │ mid │ nums[mid] │ nums[mid + 1] │ Slope Evaluation         │ Action     │
├──────┼─────┼──────┼─────┼───────────┼───────────────┼──────────────────────────┼────────────┤
│ 1    │ 0   │ 6    │ 3   │ 3         │ 5             │ 3 < 5 (Ascending Slope)  │ low = 4    │
│ 2    │ 4   │ 6    │ 5   │ 6         │ 4             │ 6 > 4 (Descending Slope) │ high = 5   │
│ 3    │ 4   │ 5    │ 4   │ 5         │ 6             │ 5 < 6 (Ascending Slope)  │ low = 5    │
└──────┴─────┴──────┴─────┴───────────┴───────────────┴──────────────────────────┴────────────┘
Loop Terminates (low == high == 5) -> Returns Index 5 (Value = 6).

Complexity Analysis (Proof of Optimum):

• Time Complexity (TC): O(log N): The search space [low, high] is strictly halved at every step. For N = 10,000,000 elements, convergence occurs in at most 24 iterations.
• Space Complexity (SC): O(1): Uses exactly three primitive integer variables on the stack (low, high, mid). Zero heap allocations and zero recursive stack frames.

Try it yourself

• Trace the execution of find_peak_optimal on [1, 2, 3, 4, 5]. Step through the values of low, mid, and high on each iteration.
• Why is it impossible for mid + 1 to cause an out-of-bounds array access inside the while (low < high) loop?

🔹 Hardware Mechanics: CPU Branch Prediction on Non-Monotonic Terrain

In standard binary search on sorted arrays, target lookups follow predictable branch directions depending on where the target lies relative to the median. In Find Peak Element, however, the array is intentionally non-monotonic:

1. Branch Predictor Behavior on Jagged Terrain

The core conditional if (nums[mid] < nums[mid + 1]) evaluates the local slope at arbitrary jump points. On jagged terrain with many alternating peaks and valleys, the branch predictor cannot easily guess whether the slope is rising or falling. However, because binary search only takes ~20 to 24 steps for 10,000,000 elements, even with multiple branch mispredictions, total execution time remains under 50 nanoseconds!

2. Cache Locality during Convergence

As the search interval shrinks (when high - low < 16), all remaining candidate elements fit into a single 64-byte L1 Data Cache Line. The final 3 to 4 iterations execute entirely within CPU registers and L1 cache hits with sub-nanosecond latency.

Try it yourself

• Explain how a branchless conditional move (CMOV instruction) can be generated by modern compilers when writing binary search.
• Compare the cache miss count between Linear Scan and Iterative Binary Search using valgrind --tool=cachegrind.

🔹 Lab: High Throughput Performance Benchmark (10,000,000 Elements)

Let’s benchmark all three approaches on an array of 10,000,000 integers containing multiple random mountain ridges. We will measure execution time over 100,000 peak queries and calculate throughput in Million operations per second.

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <iomanip>

using namespace std;

// 1. Linear Scan
int peak_linear(const vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    for (int i = 0; i < n - 1; ++i) {
        if (nums[i] > nums[i + 1]) return i;
    }
    return n - 1;
}

// 2. Recursive Divide and Conquer
int peak_recursive_helper(const vector<int>& nums, int low, int high) {
    if (low == high) return low;
    int mid = low + (high - low) / 2;
    if (nums[mid] < nums[mid + 1]) return peak_recursive_helper(nums, mid + 1, high);
    return peak_recursive_helper(nums, low, mid);
}

int peak_recursive(const vector<int>& nums) {
    return peak_recursive_helper(nums, 0, static_cast<int>(nums.size()) - 1);
}

// 3. Optimal Iterative Gradient Binary Search
int peak_optimal(const vector<int>& nums) {
    int low = 0, high = static_cast<int>(nums.size()) - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < nums[mid + 1]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    constexpr size_t N = 10000000; // 10 Million elements
    constexpr int NUM_QUERIES = 100000;

    cout << "--- CppMonk Find Peak Element Benchmark Lab ---\n";
    cout << "Generating terrain array with " << N << " elements...\n";

    // Create a terrain with a peak near the middle
    vector<int> nums(N);
    for (size_t i = 0; i < N / 2; ++i) {
        nums[i] = static_cast<int>(i * 2); // Ascending
    }
    for (size_t i = N / 2; i < N; ++i) {
        nums[i] = static_cast<int>((N - i) * 2); // Descending
    }

    cout << "Benchmark: Executing " << NUM_QUERIES << " queries on 10M elements...\n\n";

    // 1. Benchmark Recursive
    {
        auto start = chrono::high_resolution_clock::now();
        volatile int dummy = 0;
        for (int i = 0; i < NUM_QUERIES; ++i) {
            dummy = peak_recursive(nums);
        }
        auto end = chrono::high_resolution_clock::now();
        double ms = chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0;
        double ns_op = (ms * 1000000.0) / NUM_QUERIES;
        double ops_sec = (NUM_QUERIES * 1000.0) / ms;

        cout << fixed << setprecision(2);
        cout << "1. Recursive Divide & Conquer:\n";
        cout << "   Duration:    " << ms << " ms\n";
        cout << "   Avg Latency: " << ns_op << " ns / query\n";
        cout << "   Throughput:  " << (ops_sec / 1000000.0) << " Million ops/sec\n\n";
    }

    // 2. Benchmark Iterative Optimal
    {
        auto start = chrono::high_resolution_clock::now();
        volatile int dummy = 0;
        for (int i = 0; i < NUM_QUERIES; ++i) {
            dummy = peak_optimal(nums);
        }
        auto end = chrono::high_resolution_clock::now();
        double ms = chrono::duration_cast<chrono::microseconds>(end - start).count() / 1000.0;
        double ns_op = (ms * 1000000.0) / NUM_QUERIES;
        double ops_sec = (NUM_QUERIES * 1000.0) / ms;

        cout << "2. Optimal Iterative Binary Search:\n";
        cout << "   Duration:    " << ms << " ms\n";
        cout << "   Avg Latency: " << ns_op << " ns / query\n";
        cout << "   Throughput:  " << (ops_sec / 1000000.0) << " Million ops/sec\n";
    }

    return 0;
}

Output

--- CppMonk Find Peak Element Benchmark Lab ---
Generating terrain array with 10000000 elements...
Benchmark: Executing 100000 queries on 10M elements...

1. Recursive Divide & Conquer:
   Duration:    3.82 ms
   Avg Latency: 38.20 ns / query
   Throughput:  26.18 Million ops/sec

2. Optimal Iterative Binary Search:
   Duration:    2.41 ms
   Avg Latency: 24.10 ns / query
   Throughput:  41.49 Million ops/sec

Takeaway: The Optimal Iterative Binary Search runs in just 24.1 nanoseconds per query, achieving a throughput of over 41.4 Million lookups per second, outperforming recursive divide and conquer by 1.58x due to the elimination of call frame register overhead.

Try it yourself

• Compile the benchmark with -O3 -march=native and measure the latency improvement.
• Modify the terrain array to contain 5,000 alternating mini-peaks and verify that the algorithm returns a valid peak index every single time.

🔹 Key Pitfalls & Common Interview Traps

• Trap 1: Checking Both Neighbors Simultaneously: Writing if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) causes out-of-bounds exceptions when mid == 0 or mid == n - 1. By comparing only with nums[mid + 1] and using while (low < high), we guarantee that mid + 1 is always a valid in-bounds index!
• Trap 2: Using while (low <= high) with high = mid - 1: If nums[mid] > nums[mid + 1], mid itself could be the peak element. If you write high = mid - 1, you will discard the peak and get an incorrect index. Always write high = mid.
• Trap 3: Integer Overflow in Midpoint Calculation: Never write (low + high) / 2. When working with large data collections where index ranges approach INT_MAX, this triggers undefined behavior. Always write low + (high - low) / 2.
• Trap 4: Assuming the Array Must Be Sorted: Many candidates mistakenly believe binary search only works on sorted arrays. Find Peak Element proves that Binary Search works on any structure where a local decision discards half the search space with guaranteed target preservation.

Try it yourself

• Prove why mid = low + (high - low) / 2 can never equal high when low < high, ensuring mid + 1 never exceeds high.
• How would you adapt this algorithm to solve Find Peak Element II (2D Matrix Peak Finding) in O(N log M)?

🔹 Comparison of All Approaches

┌──────────────────────────────────────┬──────────────────┬──────────────────┬────────────────────────┐
│ Approach                             │ Time Complexity  │ Space Complexity │ Key Characteristics    │
├──────────────────────────────────────┼──────────────────┼──────────────────┼────────────────────────┤
│ 1. Brute Force (Linear Scan)         │ O(N)             │ O(1)             │ Naive sequential scan  │
│ 2. Recursive Divide and Conquer      │ O(log N)         │ O(log N)         │ Stack frame overhead   │
│ 3. Optimal Iterative Gradient Search │ O(log N)         │ O(1)             │ Flat loop, 41M ops/sec │
└──────────────────────────────────────┴──────────────────┴──────────────────┴────────────────────────┘

🔹 FAQs on Find Peak Element in C++

Q1: Why does Binary Search work on an unsorted array in Find Peak Element?
Binary search does not strictly require monotonic sorting; it only requires a directional decision rule that guarantees a valid solution exists in one of the two partitions. Because nums[-1] = nums[n] = -∞, following the ascending gradient (nums[mid] < nums[mid + 1]) guarantees encountering a peak.

Q2: Why do we use while (low < high) instead of while (low <= high)?
Because we set high = mid rather than mid - 1, using while (low <= high) would lead to an infinite loop when low == high == mid. while (low < high) gracefully terminates the moment the search space shrinks to a single element.

Q3: What happens if there are multiple peaks in the array?
The problem allows returning the index of any valid peak. The algorithm will follow whichever ascending slope it encounters at each step, deterministically converging to one valid peak in O(log N).

Q4: Why are duplicate adjacent elements prohibited in this problem?
If adjacent duplicate elements were allowed (e.g. [1, 2, 2, 2, 1]), encountering nums[mid] == nums[mid + 1] would create a flat plateau where neither direction is guaranteed to rise, degrading worst-case search to O(N).

Q5: Can the first or last element of the array be a peak?
Yes. Because nums[-1] = nums[n] = -∞, index 0 is a peak if nums[0] > nums[1], and index N – 1 is a peak if nums[N - 1] > nums[N - 2].

Q6: How does find_peak_optimal handle an array of size 1?
For nums = [42], low = 0 and high = 0. The while (low < high) loop does not execute, and the function immediately returns low = 0 in O(1).

Q7: What is the maximum number of iterations for an array of size 1,000,000?
The search space is halved on each iteration. log₂(1,000,000) ≈ 20, meaning the loop executes at most 20 times before converging.

Q8: How is this concept used in engineering and machine learning?
Discrete peak finding algorithms are used in audio signal processing (detecting pitch and beat frequency peaks), computer vision (edge detection via gradient crests), financial algorithmic trading (detecting local extrema in order books), and 1D optimization line searches.

🔹 Wrapping Up

Find Peak Element in C++ is a quintessential example of expanding the power of binary search beyond traditionally sorted arrays. By framing the problem as discrete gradient climbing on a mountain terrain, we reduce an O(N) search into an elegant O(log N) iterative algorithm with O(1) memory overhead. To continue sharpening your binary search skills, explore our tutorials on Search in Rotated Sorted Array I, Search in Rotated Sorted Array II, and the curated Google DSA Sheet. Practice the “Try it yourself” tasks above to reinforce your systems level problem-solving intuition!