Elements that surpass their neighboring elements in magnitude are referred to as peak elements within an array. These elements hold significant value in various scenarios like dataset recognition and algorithm enhancement. This tutorial focuses on identifying a peak element within an array using the C++ programming language.
What are Peak Elements?
An element within an array that is greater than or equal to its adjacent elements is referred to as a Peak element. In adherence to this definition, an array can potentially contain multiple peak elements, and it might be advantageous to pinpoint any of them based on the context. These circumstances can vary, with the array being either sorted or unsorted, leading to the utilization of diverse approaches for detecting peak elements.
Finding Peak Elements in an Unsorted Array:-
Exploring the identification of peak elements in an unordered array presents a broader scenario with interesting complexities, initiating our discussion on this topic.
Naive Approach:
Examining the adjacent elements of each item as we loop through the entire array is a basic approach to identifying peak elements within an unordered array. A peak element is defined as one that surpasses its neighboring elements in value.
Program:
Let's consider a C++ code to identify a peak element within an array:
#include <iostream>
#include <vector>
int findPeakElement(const std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
if ((i == 0 || arr[i] >= arr[i - 1]) && (i == n - 1 || arr[i] >= arr[i + 1])) {
return arr[i];
}
}
return -1; // No peak element found
}
int main() {
std::vector<int> arr = {1, 3, 20, 4, 1, 0};
int peak = findPeakElement(arr);
if (peak != -1) {
std::cout << "A peak element is: " << peak << std::endl;
} else {
std::cout << "No peak element found in the array." << std::endl;
}
return 0;
}
- This straightforward technique checks each item in the array, leading to an O(n) time complexity.
Using Binary Search Method:-
Binary search is a more effective method. The time complexity of this method is O(log n) . There are some following steps:
- Arr[mid] , the array's middle element, is where you should start.
- Examine it in relation to arr[mid - 1] and arr[mid + 1] , its neighbours.
- Arr[mid] is a peak element and can be returned if it is greater than both of its neighbours.
- Proceed to the left and repeat the procedure in the left subarray if arr[mid - 1] is larger than arr[mid].
- Go right and repeat the procedure in the right subarray if arr[mid + 1] is greater than arr[mid].
- By dividing the array in half at each stage in this binary search method, we are able to eliminate half of the elements in each iteration and produce an algorithm that is more efficient.
Program:
Let's consider a C++ code snippet to identify a peak element within an array by employing the binary search technique:
#include <iostream>
#include <vector>
int findPeakElement(const std::vector<int>& arr, int low, int high) {
if (low == high) {
return arr[low];
}
int mid = (low + high) / 2;
if (arr[mid] > arr[mid + 1]) {
return findPeakElement(arr, low, mid);
} else {
return findPeakElement(arr, mid + 1, high);
}
}
int main() {
std::vector<int> arr = {1, 3, 20, 4, 1, 0};
int peak = findPeakElement(arr, 0, arr.size() - 1);
if (peak != -1) {
std::cout << "A peak element is: " << peak << std::endl;
} else {
std::cout << "No peak element found in the array." << std::endl;
}
return 0;
}
Output:
Finding Maximum Elements in a Sorted Array:-
Identifying the peak elements becomes manageable when the array is sorted in either ascending or descending order.
A peak within an array that is arranged in ascending order is consistently positioned as the final element.
Here's a basic C++ implementation of that:
#include <iostream>
#include <vector>
int findPeakElement(const std::vector<int>& arr) {
return arr.back();
}
int main() {
std::vector<int> arr = {1, 3, 6, 9, 12, 15};
int peak = findPeakElement(arr);
std::cout << "A peak element is: " << peak << std::endl;
return 0;
}
- Given that this is a definite peak in this particular case, we simply output the last element of the array.
A Peak array arranged in a descending sequence:-
In an array sorted in descending order, the peak refers to the initial element.
Here's where to look for it:
#include <iostream>
#include <vector>
int findPeakElement(const std::vector<int>& arr) {
return arr[0];
}
int main() {
std::vector<int> arr = {15, 12, 9, 6, 3, 1};
int peak = findPeakElement(arr);
std::cout << "A peak element is: " << peak << std::endl;
return 0;
}
Once again, finding the maximum element in a sorted array is straightforward; we just need to consider either the first or last element based on the sorting order.
Conclusion:
An interesting subject with a diverse set of uses involves locating the peak element within an array. Determining the peak elements within an array varies based on whether the array is arranged or not. Utilizing binary search can offer an effective method to locate a peak element in an unsorted array, though the process is more straightforward in sorted arrays.
Locating peak elements efficiently is essential for enhancing algorithms and resolving problems in diverse domains such as computer science and data analysis. In C++, you can efficiently detect peak elements by understanding the concepts and methods outlined in this guide, irrespective of whether you are dealing with sorted or unsorted arrays.
