Find local minima in an array

You are given an array Arr[1 .. n] with the special property that Arr[1] ≥ Arr[2] and Arr[n − 1] ≤ Arr[n]. We say that an element Arr[x] is a local minimum if it is less than or equal to both its neighbors. Derive an algorithm in O(log n)

For example in the array 9,6,2,14,5,7,4 – 2 is a local minima as it is smaller than its left and right number 6 and 14. Similarly 5 is another local minima as it is between 14 and 7, both larger than 5. You need to find any one of the local minima.

Solution:

If the array elements are not guaranteed to be distinct, then it’s not possible to do this in O(log n) time. The reason for this is the following: suppose that you have an array where all n > 1 values are the same. In this case, none of the elements can be local minima, because no element is less than its neighbors. However, in order to determine that all values are the same, you will have to look at all the array elements, which takes O(n) time. If you use less than O(n) time, you can’t necessarily look at all the array elements.

If, on the other hand, the array elements are guaranteed to be distinct and with the given properties, you can solve this in O(log n) time using the following observations:

  1. If there is just one array element, it’s a local minimum.
  2. If there are two array elements, check each. One must be a local minimum.
  3. Otherwise, look at the middle element of the array. If it’s a local minimum, return it. Otherwise, at least one adjacent value must be smaller than this one. Recurs in the half of the array containing that smaller element (but not the middle).

int findLocalMinima(int[] arr, int start, int end)
{
	int mid = (start + end) / 2;
	if (mid - 2 < 0 && mid + 1 >= arr.length)
		return -1;
	if (arr[mid - 2] > arr[mid - 1] && arr[mid - 1] < arr[mid])
		return arr[mid - 1];
	if (arr[mid - 1] > arr[mid - 2])
		return findLocalMinima(arr, start, mid);
	else
		return findLocalMinima(arr, mid, end);
}

Complexity O(log N)

10 Thoughts on “Find local minima in an array

  1. Manoj Verma on August 1, 2013 at 11:20 pm said:

    I did not understand the question. What if array doesn’t satisfy the given property. Arr[1] ≥ Arr[2] and Arr[n − 1] ≤ Arr[n]. Wont there be a local minima?

    I can give an example where property will not be satisfied but there will be a minima:

    eg 12 3 14 5 6 5 , local minima is 3 even it is not satisfying the given property.

  2. Manish Jain on August 1, 2013 at 11:24 pm said:

    Manoj,

    you are right but its required for the question to be solved in o(log N), it satisfy given property. Else it will take O(N) ti me to solve this as u have to traverse all array elements.

  3. Vikas Chauhan on August 2, 2013 at 11:33 pm said:

    Its like a binary search.. u need to traverse only half of the array each time.

  4. Neha Garg on August 11, 2013 at 9:11 am said:

    please somebody explain this algorithm with example…

  5. Neha garg on August 11, 2013 at 4:45 pm said:

    this will find only one local minima … what if the it has two minima of both sides of middle?? ..

  6. Neha garg on August 11, 2013 at 5:34 pm said:

    according to the algorithm the code must check the middle as if this is minima or not ……… but in code implementation middle-1 th element is being checked???

  7. crazyadmin on August 13, 2013 at 12:32 pm said:

    @nidhi

    mid-1 is middle element of the array. It is specified in ques that “You need to find any one of the local minima”

  8. gli00001 on March 24, 2014 at 6:39 am said:

    try[2,1,3], this fails.

  9. Thx for the solution.
    It explained well :D

Leave a Reply

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation