Java Program to Find Local Minima in an Array
Share
Sign Up to our social questions and Answers Engine to ask questions, answer people’s questions, and connect with other people.
Login to our social questions & Answers Engine to ask questions answer people’s questions & connect with other people.
Lost your password? Please enter your email address. You will receive a link and will create a new password via email.
Please briefly explain why you feel this question should be reported.
Please briefly explain why you feel this answer should be reported.
Please briefly explain why you feel this user should be reported.
This is the Java Program to Find Local Minimas in an Array.
Given an array of integers, find out the local maxima present in the array. An element in an array is a local minima if it less than the element after it, and the element before it. For the elements at the extreme end only one check is required, that is, the element following the first element or the element before the last element. In case of two or more minima, only one of them is returned. Example: Array = [1, 2, 3, 7, 5, 6] Output: 1 or 5
The idea here is to use an algorithm, similar to the binary search. Check the middle element of the array, if it is less than the elements following it and the element preceding it, then it is the local minima, else if it is less than the preceding element, then the local minima is in the left half, else the local minima is in the right half.
1. In the function localMinima(), we initialize two variables high and low as array.length-1 and 0 respectively. 2. Using a loop while(low<=high), we first calculate the middle index. 3. Now, in the condition if((mid == 0 || array[mid-1] > array[mid]) && (mid == array.length-1 || array[mid+1] > array[mid])), we check whether the element at current middle index is a minima. 4. If the element is a minima, then we return the current middle index, otherwise using the condition else if(mid > 0 && array[mid-1] < array[mid]), we first check that we are not at the beginning of the array and finally, check if the preceding element is smaller than the current middle element. 5. If it is, we then set high to mid-1, to look in the first half of the array, otherwise, we set low to mid+1 to look for the minima in the second half of the array.
Time Complexity: O(log(n)) where n is the number of elements in the array.