156 views
Peak element in the Array in C
A peak element in an array is an element that is greater than or equal to its neighbors (if they exist). There can be multiple peak elements in an array, but we’ll find just one peak element in this example. Here’s a C program to find a peak element in an array using a binary search approach:
C
#include <stdio.h>
int findPeakElement(int arr[], int low, int high, int n) {
// Handle base cases
if (low < 0 || high >= n) {
return -1; // Invalid indices
}
int mid = low + (high - low) / 2;
// Check if the middle element is a peak
if ((mid == 0 || arr[mid] >= arr[mid - 1]) && (mid == n - 1 || arr[mid] >= arr[mid + 1]))
{
return arr[mid];
}
// If the element to the right is greater, move right
if (mid < n - 1 && arr[mid] < arr[mid + 1]) {
return findPeakElement(arr, mid + 1, high, n);
}
// Otherwise, move left
return findPeakElement(arr, low, mid - 1, n);
}
int main() {
int arr[] = {1, 3, 20, 4, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
int peak = findPeakElement(arr, 0, n - 1, n);
if (peak != -1) {
printf("A peak element is: %d\n", peak);
} else {
printf("No peak element found.\n");
}
return 0;
}In this program:
- The
findPeakElementfunction performs a binary search to find a peak element in the array. - The base cases check for invalid indices and return
-1in such cases. - In the binary search, we calculate the middle index
midand compare the element atmidwith its neighbors. - If the middle element is a peak (greater than or equal to its neighbors), we return it.
- If the element to the right is greater than the middle element, we search for a peak in the right subarray; otherwise, we search in the left subarray.
- In the
mainfunction, a sample array is provided, and thefindPeakElementfunction is called to find and print a peak element if one exists.
You can modify the arr array to test the program with different inputs.