Question 23 : Find local minima in array

A local minimum is less than its neighbors

For example:

Input :
 
int [] arr = {10, 5, 2, 6, 13, 16, 7};
Output: 2
 
int []arr = {11,12,13,14};
Output: 11
 
int []arr = {10};
Output: 10
 
int []arr = {8,6};
Output: 6

Solution

Naive approach

You can use for loop and compare neighbor elements, you will get the local minima.
Worst-case time complexity will be o(n).

Efficient approach

You can use binary search to find local minima.

Worst-case time complexity will be o(og n).
Here is a simple algorithm

• Find the mid element
• If mid element is less then both the neighbor then return it.
• If mid element is greater then its left neighbor, then go left
• else go right.

public class LocalMinima {
 
    public int findLocalMinima(int [] arr, int start, int end){
 
        /*find the mid index*/
        int mid = start + (end-start)/2;
        int size = arr.length;
 
        /*check the local minima 
         *first check if left and right neighbor exists */
        if((mid==0 || arr[mid-1]>arr[mid]) &&
                (mid==size-1 || arr[mid+1]>arr[mid]))
            return arr[mid];
        /* check if left neighbor is less than mid element, if yes go left */
        else if(mid>0 && arr[mid]>arr[mid-1]){
            return findLocalMinima(arr, start, mid);
        }
        else { 
            /*check if right neighbor is greater than mid element, if yes go right */
            return findLocalMinima(arr, mid+1, end);
        }
    }
 
    public static void main(String[] args) {
        LocalMinima l = new LocalMinima();
        int [] arr = {10, 5, 3, 6, 13, 16, 7};
        System.out.println("Local Minima is: " + l.findLocalMinima(arr,0,arr.length));
    }
}

When you run the above program, you will get below output.

Local Minima is: 3

That’s all about how to find the local minima in an array

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This

• Facebook
• Twitter
• Linkedin
• Pinterest