If you want to practice data structure and algorithm programs, you can go through 100+ data structure and algorithm programs.

In this post, we will see how to find the local minima in the array.

## Problem

An element is local minima if it is less than its neighbors.

int [] arr = {10, 5, 3, 6, 13, 16, 7};

Output: 2

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(log n).

Here is simple algorithm

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
package org.arpit.java2blog; 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 above program, you will get below output.

Local Minima is: 3

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