Java Program to Find Local Minima in an Array

«
»

This is the Java Program to Find Local Minimas in an Array.

Problem Description

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.

advertisement

Example:
Array = [1, 2, 3, 7, 5, 6]

Output:
1 or 5

Problem Solution

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.

Program/Source Code
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here is the source code of the Java Program to Find Local Minima in an Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Find Local Minimas in an Array
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class LocalMinima {
  8.     // Function to return the index of the local minima
  9.     static int localMinima(int[] array){
  10.         int low,mid,high;
  11.         low = 0;
  12.         high = array.length-1;
  13.         mid = (low + high)/2;
  14.         int ans;
  15.         while(low<=high){
  16.             mid = (low + high)/2;
  17.             if((mid == 0 || array[mid-1] > array[mid]) 
  18.                 && (mid == array.length-1 || array[mid+1] > array[mid])){
  19.                 return mid;
  20.             }
  21.             else if(mid > 0 && array[mid-1] < array[mid]){
  22.                 high = mid-1;
  23.             }
  24.             else{
  25.                 low = mid+1;
  26.             }
  27.         }
  28.         return -1;
  29.     }
  30.     // Function to read user input
  31.     public static void main(String[] args) {
  32.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  33.         int size;
  34.         System.out.println("Enter the size of the array");
  35.         try {
  36.             size = Integer.parseInt(br.readLine());
  37.         } catch (Exception e) {
  38.             System.out.println("Invalid Input");
  39.             return;
  40.         }
  41.         int[] array = new int[size];
  42.         System.out.println("Enter array elements");
  43.         int i;
  44.         for (i = 0; i < array.length; i++) {
  45.             try {
  46.                 array[i] = Integer.parseInt(br.readLine());
  47.             } catch (Exception e) {
  48.                 System.out.println("An error occurred");
  49.                 return;
  50.             }
  51.         }
  52.         int index = localMinima(array);
  53.         System.out.println("The local minima is " + array[index]);
  54.     }
  55. }
Program Explanation

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.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
advertisement

Time Complexity: O(log(n)) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Positive test Case - local minima is not at the extreme ends):
 
Enter the size of the array
8
Enter array elements
23
12
11
10
13
5
57
58
The local minima is 10
 
Case 2 (Positive test Case - local minima is at the beginning of the array):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The local minima is 1
 
 
Case 3 (Positive test Case - local minima is at the end of the array):
 
Enter the size of the array
5
Enter array elements
9
8
7
6
5
The local minima is 5

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.