Local minimum in unsorted array

Question

Suppose I have an array a[i] for 0<=i<=n-1. Can I find, using an algorithm of complexity O(log n), i such that 1<=i<=n-2, a[i]<=a[i+1] and a[i]<=a[i-1]? That is, can I find a local minima in logarithmic time?

_{Note: I edited the question (which had changed many times) to be one that could reasonably be answered. I removed the strange end conditions that appeared in an earlier version because this version is simpler and yet loses no generality.}

Answer 1

First, we need to consider how a local minimum is defined:

a[i] < a[i-1] and a[i] < a[i+1]

From this condition, we see that if we were to plot the array on an X/Y graph (X=index, Y = value), local minimums would be at the valleys. Therefore, to ensure there is a local minimum, we must guarantee that a change in slope sign (from decreasing to increasing) exists.

If you know the endpoint slope behavior of a range, you know if there is a local minimum within. In addition, your array must have the behavior decreasing slope sign from a[0] to a[1] and increasing slope sign from a[n-1] to a[n] or the problem is trivial. Consider:

a = [1,2,3,4,5] (increasing, increasing) a[0] is an LM
a = [5,4,3,2,1] (decreasing, decreasing) a[n] is an LM
a = [1,2,2,2,1] (increasing, decreasing) a[0] and a[n] are LMs

I think this should be enough inspiration for you to complete the method.

Note that expanding this method is good only for unique values, for example an array of all 1s, it will not have O(log n) run time unless you do some edge case detection.

Answer 2

Unless your array has other constraints on it, you can't find local minimum in O(log n) without (at least) linear time preprocessing, because in worst case you need to check every single element in your array. It is not difficult to prove this statement formally, the idea is to construct such array, for each scanning method, that this method will work in linear time on constructed array.

For example, imagine if you're doing simple scan in array of size n from the beginning to the end: if your minimum is at n-1-th position, then you'll discover it only after n-1 iterations, which is O(n)

http://www.careercup.com/question?id=8223978