Find the local minima in array

Previous
Next

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.


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

Join Our News Letter – Stay Updated

Subscribe to Awesome Java Content.




Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog