JAVA CODING on Binary Search . 1. Given an array of integers. Find a mountain to
ID: 3820580 • Letter: J
Question
JAVA CODING on Binary Search .
1. Given an array of integers. Find a mountain top element in it. An array element is moutain top element if it is NOT smaller than its neighbors.ie if an element is greater than its left and right element. For corner elements, we need to consider only one neighbor. For example, for input array {5, 10, 20, 15}, 20 is the only peak element. For input array {10, 25, 15, 7, 36, 75, 53}, there are two mountain top elements: 25 and 75.Note that we need to return any one of the mountain top element .
Following corner cases give better idea about the problem.
If input array is sorted in strictly increasing order, the last element is always a mountain top element. For example, 50 is mountain top element in {10, 20, 30, 40, 50}.
If input array is sorted in strictly decreasing order, the first element is always a mountain top element. 100 is the mountain top element in {100, 80, 60, 50, 20}.
If all elements of input array are same, every element is a mountain top element. So return an element
Your input should have arrays, of each test case described above and should output the value for each of the test case.
Instructions:-
Please write approach with 2-3 sentences
Please paste output screenshot
Explanation / Answer
HI, Please find my implementation.
Please let me know in case of ny issue.
Algorithm:
We can use Divide and Conquer to find a peak in O(Logn) time.
The idea is Binary Search based, we compare middle element with its neighbors.
If middle element is not smaller than any of its neighbors, then we return it.
If the middle element is smaller than the its left neighbor, then there is always a peak in left half
If the middle element is smaller than the its right neighbor, then there is always a peak in right half
public class MoutainTopElement
{
// A binary search based function that returns index of a peak
// element
static int findMoutainTopUtil(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 neighbours (if neighbours
// exist)
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 neighbor is
// greater than it,then left half must have a peak element
else if (mid > 0 && arr[mid-1] > arr[mid])
return findMoutainTopUtil(arr, low, (mid -1), n);
// If middle element is not peak and its right neighbor
// is greater than it, then right half must have a peak
// element
else return findMoutainTopUtil(arr, (mid + 1), high, n);
}
// A wrapper over recursive function findPeakUtil()
static int findMoutainTop(int arr[], int n)
{
return findMoutainTopUtil(arr, 0, n-1, n);
}
// Driver method
public static void main (String[] args)
{
int arr[] = {10, 25, 15, 7, 36, 75, 53};
int n = arr.length;
System.out.println("Moutain top element is " +
arr[findMoutainTop(arr, n)]);
}
}
/*
Sample run:
Moutain top element is 25
*/
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.