Let X[1: n] be an array of real numbers. An entry X[k], where 1<k<n, is called a
ID: 3869924 • Letter: L
Question
Let X[1: n] be an array of real numbers. An entry X[k], where 1<k<n, is called a peak if X[k 1] < X[k] > X[k+1] ; the value
k is called in the position of the peak. The highest peak is the peak of the largest value. Note that an array may have one
peak, many peaks, or no peaks at all. a. Give a divide-and-conquer algorithm for finding the positions of all the peaks in
an input array, and analyze its time complexity. b. Give a divide-and-conquer algorithm for finding the position of the
highest peak in an input array, and analyze its time complexity.
Explanation / Answer
Algorithm for finding peak Element using Divide and conquer approach
//This function would return the index of the peak element and works on the same algo as of binary search
int peakfindutil(int a[], int low, int high, int n)
{
// Now index of the middle element is to be evaluated
int mid = low + (high - low)/2; /* (low + high)/2 */
// Now the middle element we found has to be compared to its neighbours (only in the case they exist :-))
if ((mid == 0 || a[mid-1] <= a[mid]) &&
(mid == n-1 || a[mid+1] <= a[mid]))
return mid;
//now two cases arise 1.if the middle element is not greater than left element
//2. if the middle element is not greater than right element
// its left neighbour is greater and peak is not the middle element
// than it, then left half must possess a peak element
else if (mid > 0 && a[mid-1] > a[mid])
return peakfindutil(a, low, (mid -1), n);
// its right neighbour is greater and peak is not the middle element
// than it, then right half must possess a peak element
else return peakfindutil(a, (mid + 1), high, n);
}
// A wrapper over recursive function peakfindutil()
int peakfind(int a[], int n)
{
return peakfindutil(a, 0, n-1, n);
}
/* Main Program*/
int main()
{
int a[] = {1, 3, 20, 4, 1, 0};
int n = sizeof(a)/sizeof(a[0]);
printf("Index of a peak point is %d", peakfind(a, n));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.