Let A[1 . . . n] be an array of n distinct integers. We say that A is peaked, if

Question

Let A[1 . . . n] be an array of n distinct integers. We say that A is peaked, if there exists an index 1 k n such that:

(1) For all 1 i < k, A[i] < A[i + 1] and
(2) for all k < i n, A[i 1] > A[i]. That is, the array increases until k and decreases afterward. Call the index k the peak of A.

Describe an algorithm which in O(log n) time finds the peak of a given peaked array A[1 . . . n] consisting of n distinct integers. Specifically, give short descriptions of how your algorithm works, why it is correct, and why it achieves the stated running time.

Explanation / Answer

//Program to find a peak element element in a given array using divide and conquer approach
import java.util.*;
import java.lang.*;
import java.io.*;

class PeakIndex
{
// search function based on binary search that returns index of a peak
static int find_possible_peak(int arr[], int low, int high, int n)
{
// Find index of middle element
int mid = low + (high - low)/2; /* (low + high)/2 */

// Compare middle element with its adjacent element
if ((mid == 0 || arr[mid-1] <= arr[mid]) && (mid == n-1 ||
arr[mid+1] <= arr[mid]))
return mid;

// If middle element is not peak and its left adjacent is
// greater than it,then left half must have a peak element
else if (mid > 0 && arr[mid-1] > arr[mid])
return find_possible_peak(arr, low, (mid -1), n);

// If middle element is not peak and its right adjacent
// is greater than it, then right half must have a peak
// element
else return find_possible_peak(arr, (mid + 1), high, n);
}

// A wrapper over recursive function find_possible_peak()
static int Peak(int arr[], int n)
{
return find_possible_peak(arr, 0, n-1, n);
}

// Driver method
public static void main (String[] args)
{
int arr[] = {1, 3, 20, 4, 1, 0};
int n = arr.length;
System.out.println("Index of a peak element is " +
Peak(arr, n));
}
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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