Find the local minima in a given array

Objec­tive:  Given an array of integer write an algorithm to find the local minima.

Local Minima: An element is considered as local minima if it is less than both of its neighbors (if neighbors exist).


int [] arrA = {11, 4, 2, 5, 11, 13, 5};
Output: Local Minima is: 2

int []arrA = {1,2,3,4};
Output: 1

int []arrA = {3};
Output: 3

int []arrA = {6,4};
Output: 4

NOTE: There could be many local minima’s, we need to find any one.


Naïve: Use for loop and compare every element with its neighbor.

Time Complexity – O(n)

Binary Search Approach:

  • Check if mid element is smaller than its left and right neighbors.
  • If left neighbor is less than the mid element then make a recursive call to the left half of the array. (There will be at least one local minima in the left half, take few examples to check)
  • If right neighbor is less than the mid element then make a recursive call to the right half of the array.

Time Complexity – O(logn)



Local Minima is: 2


Top Companies Interview Questions..-


If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

4 Responses

  1. Johannes Weber says:

    I’d avoid recursion and do the binary search in a while loop for
    – improving the readability and
    – traceability and
    – avoid long callstacks

  2. VP says:

    causes stack overflow for input array: {11, 2, 2, 5, 11, 1, 5};

  3. Tài Nguyễn Thành says:

    i find bug when input has duplicate or has no element is satisfy

  4. SANDIP KUMAR says:

    why we using binary search?
    i think we can’t use binary search because array may not be sorted always

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: