Find the local minima in array

Previous
Next

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

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.

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

Previous
Next

Add Comment