Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the local minima in a given array

Objec­tive:  Given an array of inte­ger write an algo­rithm to find the local minima.

Local Min­ima: An ele­ment is con­sid­ered as local min­ima if it is less than both of its neigh­bors (if neigh­bors exist).

Exam­ple:

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.

Approach:

Naïve: Use for loop and com­pare every ele­ment with its neighbor.

Time Com­plex­ity – O(n)

Binary Search Approach:

  • Check if mid ele­ment is smaller than its left and right neighbors.
  • If left neigh­bor is less than the mid ele­ment then make a recur­sive call to the left half of the array. (There will be at least one local min­ima in the left half, take few exam­ples to check)
  • If right neigh­bor is less than the mid ele­ment then make a recur­sive call to the right half of the array.

Time Com­plex­ity – O(logn)

Code:

Out­put:

Local Minima is: 2

Ref­er­ence: http://www.geeksforgeeks.org/find-local-minima-array/

You may also like...