Find the Peak Element in an Array
Finding a peak element in an array is a classic algorithmic problem. A peak element is defined as an element that is strictly greater than its immediate neighbors. Using a highly efficient binary search approach, we can determine the index of a peak element in an array with an O(log n) time complexity, drastically outperforming linear search methods. Below, we break down the problem and provide a clean C++ solution.
Problem Statement
Given an array arr[] where no two adjacent elements are the same, find the index of a peak element. An element is considered to be a peak if it is greater than its adjacent elements (if they exist). If there are multiple peak elements, return the index of any one of them. The output will be "true" if the index returned by your function is correct; otherwise, it will be "false".
Note: Consider the element before the first element and the element after the last element to be negative infinity.
Examples
Input: arr = [1, 2, 4, 5, 7, 8, 3]
Output: true
Explanation: arr[5] = 8 is a peak element because arr[4] < arr[5] > arr[6].Input: arr = [10, 20, 15, 2, 23, 90, 80]
Output: true
Explanation: arr[1] = 20 and arr[5] = 90 are peak elements because arr[0] < arr[1] > arr[2] and arr[4] < arr[5] > arr[6]. Input: arr = [1, 2, 3]
Output: true
Explanation: arr[2] is a peak element because arr[1] < arr[2] and arr[2] is the last element, so it has negative infinity to its right.Constraints
- 1 ≤ arr.size() ≤ 106
- -231 ≤ arr[i] ≤ 231 - 1
For more details, visit the problem on LeetCode or GeeksforGeeks.
Optimal C++ Solution using Binary Search
Algorithm: We employ a binary search approach to locate a peak element in O(log n) time complexity. By comparing the middle element with its neighbors, we can safely discard half of the search space, knowing a peak must exist in the remaining half.
//
// Optimal Binary Search C++ Implementation
//
#include <iostream>
#include <vector>
using namespace std;
int findPeakElement(const vector<int>& arr) {
int n = arr.size();
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if the mid element is a peak
if ((mid == 0 || arr[mid] > arr[mid - 1]) &&
(mid == n - 1 || arr[mid] > arr[mid + 1])) {
return mid; // Peak found
}
// If the left neighbor is greater, search on the left side
if (mid > 0 && arr[mid - 1] > arr[mid]) {
high = mid - 1;
}
// Otherwise, search on the right side
else {
low = mid + 1;
}
}
return -1; // This should never be reached
}
int main() {
vector<int> arr = {1, 2, 4, 5, 7, 8, 3};
int peakIndex = findPeakElement(arr);
cout << "Peak element index: " << peakIndex << endl;
return 0;
}Frequently Asked Questions (FAQ)
What is a peak element in an array?
A peak element is an element that is strictly greater than its neighbors. For the first and last elements, we assume their outer neighbors are negative infinity.
Why does binary search work for finding a peak element?
Binary search works because the problem guarantees no two adjacent elements are equal. If a middle element is smaller than its right neighbor, a peak must exist on the right side. Otherwise, a peak must exist on the left side (including the middle).
Can an array have multiple peak elements?
Yes, an array can have multiple peak elements. Our algorithm will return the index of any one of these peaks.