Finding a Peak Element in an Array in C++

This article explores the problem of finding a peak element in an array. A peak element is defined as an element that is not smaller than its neighbors. Given an array, the goal is to find any one of the peak elements within it. We will present an efficient solution using a modified binary search approach in C++.

Fundamental Concepts / Prerequisites

Before diving into the solution, a basic understanding of the following concepts is beneficial:

• Arrays: Understanding how arrays store data sequentially.
• Binary Search: Familiarity with the binary search algorithm and its divide-and-conquer strategy.
• Conditional Statements: Knowledge of `if` and `else` statements for decision-making in code.

Core Implementation/Solution

We will use a modified binary search algorithm to efficiently find a peak element. The algorithm works by repeatedly dividing the search interval in half and checking if the middle element is a peak. If it is, we return it. Otherwise, we move to the half that contains a potentially higher value.

#include <iostream>
#include <vector>

int findPeakElement(const std::vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) / 2; // To prevent potential overflow

        if (nums[mid] < nums[mid + 1]) {
            // The peak lies to the right
            left = mid + 1;
        } else {
            // The peak lies to the left (or mid is a peak)
            right = mid;
        }
    }

    // At the end of the loop, left and right converge to a peak element
    return left;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 1};
    int peakIndex = findPeakElement(arr);
    std::cout << "Peak element index: " << peakIndex << std::endl;  // Output: 2
    std::cout << "Peak element value: " << arr[peakIndex] << std::endl;  // Output: 3

    std::vector<int> arr2 = {1, 2, 1, 3, 5, 6, 4};
    peakIndex = findPeakElement(arr2);
    std::cout << "Peak element index: " << peakIndex << std::endl;  // Output: 5
    std::cout << "Peak element value: " << arr2[peakIndex] << std::endl;  // Output: 6

    return 0;
}

Code Explanation

The findPeakElement function takes a vector of integers nums as input and returns the index of a peak element.

1. **Initialization:** We initialize two pointers, left and right, to the start and end of the array, respectively.

2. **Binary Search Loop:** The while (left < right) loop performs the binary search. The loop continues as long as the left pointer is strictly less than the right pointer.

3. **Midpoint Calculation:** Inside the loop, we calculate the middle index mid using left + (right - left) / 2. This avoids potential integer overflow compared to (left + right) / 2.

4. **Comparison:** We compare the element at mid with the element at mid + 1.

• If nums[mid] < nums[mid + 1], it means the peak element lies to the right of mid. Therefore, we update left = mid + 1.
• Otherwise, if nums[mid] >= nums[mid + 1], it means the peak element lies to the left of mid or mid itself is a peak. Therefore, we update right = mid.

5. **Return Value:** When the loop terminates (i.e., left == right), both left and right will be pointing to a peak element. We return the value of left (or right, as they are equal).

Complexity Analysis

The time complexity of the findPeakElement function is O(log n), where n is the number of elements in the array. This is because we are using binary search, which divides the search space in half with each iteration.

The space complexity is O(1), as we are only using a constant amount of extra space for the left, right, and mid variables, regardless of the size of the input array.

Alternative Approaches

A simple alternative approach is to iterate through the array and check for each element if it is greater than its neighbors. This approach has a time complexity of O(n), which is less efficient than the binary search approach for larger arrays. The space complexity would still be O(1).

Conclusion

In this article, we explored how to find a peak element in an array using C++. We implemented an efficient solution based on a modified binary search algorithm. The solution has a time complexity of O(log n) and a space complexity of O(1). Understanding the properties of peak elements and leveraging binary search allows for a significant performance improvement compared to a linear search approach.