algorithm - Find local minima in an array

Question

Given an array of integers, find the local minima. An element A[i] is defined as a local minimum if A[i-1] > A[i] and A[i] < A[i+1] where i = 1...n-2. In case of boundary elements, the number has to be just smaller than its adjacent number.

I know if there is only one local minimum, then we can solve with modified binary search. But if it is known that there exist multiple local minima in the array, can it be solved in O(log n) time?

Answer 1

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, you can solve this in O(log n) time using the following observations:

1. If there is just one element, it's guaranteed to be a local minimum.
2. If there are multiple elements, look at the middle element. If it's a local minimum, you're done. Otherwise, at least one of the elements next to it must be smaller than it. Now, imagine what would happen if you were to start at one of the smaller elements and progressively move toward one of the ends of the array in the direction away from the middle element. At each step, either the next element is smaller than the previous, or it will be bigger. Eventually, you will either hit the end of the array this way, or you will hit a local minimum. Note that this means that you could do this to find a local minimum. However, we're not actually going to do that. Instead, we'll use the fact that a local minimum will exist in this half of the array as a justification for throwing away one half of the array. In what remains, we are guaranteed to find a local minimum.

Consequently, you can build up the following recursive algorithm:

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. Recurse in the half of the array containing that smaller element (but not the middle).

Notice that this has the recurrence relation

T(1) ≤ 1

T(2) ≤ 1

T(n) ≤ T(n / 2) + 1

Using the Master Theorem, you can show that this algorithm runs in time O(log n), as required.

Hope this helps!

Please also notice that this algorithm only works if edges of the array count as local minima if they are smaller than the adjacent element.