## Wednesday, May 4, 2022

### 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.