Peak Element - C++ Solution

1. Introduction

In this blog post, we will discuss how to efficiently find a peak element in an integer array. A peak element is an element that is greater than its neighbors. This problem is a good example of how a simple modification of the binary search algorithm can be applied to a different context.

Problem

Given an integer array A, the task is to find a peak element in it. An element is considered a peak if it is greater than its neighboring elements. The array may have multiple peak elements, and any one of them can be reported as the output.

2. Solution Steps

1. Use binary search to find a peak element.

2. Check if the middle element is a peak. If so, return it.

3. Otherwise, move to the half of the array which has a higher element next to the middle, as a peak is guaranteed to be there.

4. Continue this process until a peak element is found.

5. If no peak element exists (in case of an empty array), return -1.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find a peak element
int findPeakElement(const vector<int>& A) {
    int low = 0, high = A.size() - 1;

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

        // Check if the mid element is a peak
        if ((mid == 0 || A[mid - 1] <= A[mid]) && (mid == A.size() - 1 || A[mid + 1] <= A[mid])) {
            return A[mid];
        }

        // Move to the right half if the element on the right is greater
        if (mid < A.size() - 1 && A[mid + 1] > A[mid]) {
            low = mid + 1;
        } else {
            // Move to the left half otherwise
            high = mid - 1;
        }
    }

    return -1; // No peak element found
}

int main() {
    vector<int> nums = {8, 9, 10, 2, 5, 6};
    cout << "Peak Element: " << findPeakElement(nums) << endl;
    return 0;
}

Output:

Peak Element: 10

Explanation:

The function findPeakElement performs a modified binary search to identify a peak element in the array. It checks whether the middle element of the current subarray is greater than its neighbors. If not, it moves to the part of the array that has a greater adjacent element. For example, in the array [8, 9, 10, 2, 5, 6], either 10 or 6 can be a peak element, and the function returns one of them. In case of an empty array, the function correctly returns -1, indicating no peak element exists.