Suppose you are given an array A with n entries, with each entry holding a disti

Question

Suppose you are given an array A with n entries, with each entry holding a distinct number. You are told that the sequence of values A[1], A[2], …, A[n] is unimodal: for some index p between 1 and n, the values in the array entries increase up to position p in A and then decrease the remainder of the way until position n. For example, the array A = [1 3 4 5 6 7 8 5 2] is unimodal, with the entries increasing up to position A[7] = 8 and decreasing afterwards.

*Write a program (in C++ or Java) that finds the “peak entry” p without having to read the entire array. Your program should run in O(logn).

Explanation / Answer

#include <stdio.h>

// recursive function to find peak using binary search logic
int peak(int t[], int l, int h, int n)
{
int m = l + (h - l)/2; // finding mid
  
// following binary search logic comparing with middle value
if ((m == 0 || t[m-1] <= t[m]) &&
(m == n-1 || t[m+1] <= t[m]))
return m;
else if (m > 0 && t[m-1] > t[m])
return peak(t, l, (m -1), n);
else return peak(t, (m + 1), h, n);
}

int main()
{
// put your array here
int a[] = {1, 3, 7, 14, 20, 21, 100, 99, 19, 4, 1, 0};
int n = sizeof(a)/sizeof(a[0]);
printf("Peak point is %d", a[peak(a, 0, n-1, n)]); // prints output
return 0;
}

/*

Sample Output

Peak point is 100

*/

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.