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.

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

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.

```
 
```

//Java Program to Find Local Minimas in an Array

```
 
```
```
import java.io.BufferedReader;
```
```
import java.io.InputStreamReader;
```
```
 
```
```
public class LocalMinima {
```

    // Function to return the index of the local minima

    static int localMinima(int[] array){

```
        int low,mid,high;
```
```
        low = 0;
```
```
        high = array.length-1;
```
```
        mid = (low + high)/2;
```
```
        int ans;
```
```
        while(low<=high){
```
```
            mid = (low + high)/2;
```

            if((mid == 0 || array[mid-1] > array[mid])

                && (mid == array.length-1 || array[mid+1] > array[mid])){

```
                return mid;
```
```
            }
```

            else if(mid > 0 && array[mid-1] < array[mid]){

```
                high = mid-1;
```
```
            }
```
```
            else{
```
```
                low = mid+1;
```
```
            }
```
```
        }
```
```
        return -1;
```
```
    }
```
```
    // Function to read user input
```

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

```
        int size;
```

        System.out.println("Enter the size of the array");

```
        try {
```

            size = Integer.parseInt(br.readLine());

```
        } catch (Exception e) {
```

            System.out.println("Invalid Input");

```
            return;
```
```
        }
```
```
        int[] array = new int[size];
```

        System.out.println("Enter array elements");

```
        int i;
```

        for (i = 0; i < array.length; i++) {

```
            try {
```

                array[i] = Integer.parseInt(br.readLine());

```
            } catch (Exception e) {
```

                System.out.println("An error occurred");

```
                return;
```
```
            }
```
```
        }
```
```
        int index = localMinima(array);
```

        System.out.println("The local minima is " + array[index]);

```
    }
```
```
}
```

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

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.

« Prev - Java Program to Print Even Elements at Even Index

» Next - Java Program to Rotate an Array by n Elements

Related Posts:

Recommended Articles: