Suppose you are given an array A with n entries, with each entry holding a disti
ID: 3576156 • Letter: S
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 Java or C++) that finds the “peak entry” p without having to read the entire array. Your program should run in O(logn).
Explanation / Answer
Hi, fims my Java implementation.
Please let me know in case of any issue.
public class PeakElement {
public static int peakElement(int arr[], int low, int high)
{
/* Base Case: Only one element is present in arr[low..high]*/
if (low == high)
return arr[low];
/* If there are two elements and first is greater then
the first element is maximum */
if ((high == low + 1) && arr[low] >= arr[high])
return arr[low];
/* If there are two elements and second is greater then
the second element is maximum */
if ((high == low + 1) && arr[low] < arr[high])
return arr[high];
int mid = (low + high)/2; /*low + (high - low)/2;*/
/* If we reach a point where arr[mid] is greater than both of
its adjacent elements arr[mid-1] and arr[mid+1], then arr[mid]
is the maximum element*/
if ( arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])
return arr[mid];
/* If arr[mid] is greater than the next element and smaller than the previous
element then maximum lies on left side of mid */
if (arr[mid] > arr[mid + 1] && arr[mid] < arr[mid - 1])
return peakElement(arr, low, mid-1);
else // when arr[mid] is greater than arr[mid-1] and smaller than arr[mid+1]
return peakElement(arr, mid + 1, high);
}
public static void main(String[] args) {
int A[] = {1, 3, 4, 5, 6, 7, 8, 5, 2};
System.out.println("Peak element: "+ peakElement(A, 0, A.length-1));
}
}
/*
Modify the standard Binary Search algorithm for the given type of arrays.
i) If the mid element is greater than both of its adjacent elements, then mid is the maximum.
ii) If mid element is greater than its next element and smaller than the previous element then
maximum lies on left side of mid.
iii) If mid element is smaller than its next element and greater than the previous element then maximum
lies on right side of mid.
Time Complexity: O(Logn)
Sample output:
Peak element: 8
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.