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 am such that 1 <= i <= n-2, a [i] <= a [i + 1] and a [i] <= a [I -1]? That is, can one find local minima in logarithmic time?

_{Note I edited the question (which has changed many times) so that I can answer it. I removed the strange end conditions that appeared in the earlier version, because this version is simpler and yet has no commonality.}

Answer 1

First, we need to consider how the local minimum is determined:

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

From this condition, we see that if we built an array on the X / Y chart (X = index, Y = value), local minima would be in the valleys. Therefore, to ensure a local minimum, we must ensure that there is a change in the sign of the slope (from decreasing to increasing).

If you know the tilt behavior of the end point of the range, you know if there is a local minimum inside. In addition, your array must have behavior decreasing the sign of the slope from [0] to [1] and increasing the sign of the slope from [n-1] to [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 this method.

Note that the extension of this method is good only for unique values, for example an array of all 1s, it will not have O (log n) runtime if you do not find any extreme case.

Answer 2

Unless your array has other restrictions on it, you cannot find a local minimum in O (log n) without (at least) linear temporary preprocessing, because in the worst case, you need to check every single element in your array. It is easy to prove this statement formally, the idea is to build such an array for each scanning method, so that this method works in linear time for the constructed array.

For example, imagine if you are doing a simple scan in an array of size n from beginning to end: if your minimum is at the n-1 position, then you will only find it after n-1 iterations O(n)

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

Answer 3

It is solved similarly to the binary search method in O (log n), but only if you have one local minimum and different numbers in the array. Your array should look something like this:

 8 5 4 3 [1] 2 6 9 

One of them is a local minimum.

Check boundaries. if a [0] a [1], a [1] is a local minimum. if [n-1]> a [n], a [n] is a local minimum. If none of these conditions is true, start sharing:

Check [n / 2] if [n / 2]> a [n / 2 + 1], then the local minimum on the right side of the array, otherwise on the left side. Then solving the problem recursively.

Answer 4

I cannot refute the work of this solution, so I would be happy if someone could.

Consider an array 'a' indexed from 1 to n.

 low = 1 high = n mid = (low + high)/2 

Without losing too much generality, I'm going to assume that the values ​​of the array are different. So, in the middle, a [mid-1], [mid], [mid + 1] can be similar:

 Case 1: /\ Case 2: \/ Case 3: / / Case 4: \ \ Case 5(boundary): / Case 6(boundary): \ 

& m = mid

Each case can be verified using the following conditions:

 1: a[m] > a[m-1] && a[m] > a[m+1] 2: a[m] < a[m-1] && a[m] < a[m+1] 3: a[m] > a[m-1] && a[m] < a[m+1] 4: a[m] < a[m-1] && a[m] > a[m+1] 

I will also ignore the explanation of the boundary cases:

The second case is the desired case when a [m] are local minima

for the third case:

there are always local minima on the left, therefore, set h = m - 1 and continue

for the 4th case:

there are always local minima on the right, therefore l = m + 1 and continue

for the 1st case, I can go in any direction: I believe that this works, because the only time you reduce the segment that you are considering is when you are sure that there are local lows in the reduced segment, so in the segment you are looking for will always have local lows.

Note. This will only work for finding single local minimums, not for each local minimum. For the latter case, O (n) is required, since you definitely need to see the entire array at least once.

Answer 5

The problem can be solved in O(logn) with a kind of binary search.

The trick is very well explained in http://www.dsalgo.com/2013/03/find-local-minima-in-array.html . This website provided a recursive implementation.

I really came up with another iterative implementation as follows.

 #include <cstdio> #include <vector> using std::vector; int SearchLocalMinima(const vector<int>& sspace) { if (sspace.size() < 2) return -1; if (sspace.size() == 2) return 0; int L = 0, U = sspace.size() - 1; while (L<U) { int M = L + (U - L) / 2; if (M - 1 == L) { if (sspace[M] <= sspace[M + 1]) return M; else return M + 1; } else { if (sspace[M] <= sspace[M + 1]) U = M + 1; else L = M; } } return -1; } int main() { vector<int> values{64, 14, 52, 27, 71, 19, 63, 1, 16, 57}; printf("Local minima: %d\n", SearchLocalMinima(values)); return 0; } 

Output: Local minima: 7

Answer 6

Edit: This only works if the local minimum is defined as "<=" and not "<". However, with "<" there is no solution. Therefore, I will keep this here, bearing in mind that it does not solve the (insoluble) OP issue.

---

The next division and rest method is to find the local minimum in O (log n) if at least one local minimum exists.

• Consider the first, last and middle elements (let's call them A, B, C).
• If A is the smallest of the three, continue with the first half of your array.
• Otherwise, if C is the smallest of the three, continue with the second half of your array.
• Otherwise (i.e. B is the smallest of the three), check if the middle element of the first half (D) is lower than B, and use the left half in this case.
• Otherwise, check if the middle element of the right half (E) is lower than B, and use the other half in this case.
• Otherwise, continue from the elements from D to E (where B is in the middle).

In each case 2. - 6. you continue an element that has higher elements on the left and on the right (although not necessarily directly), or is located on the border. Each time, when the number of elements examined is halved, then O (log n). In the end, you will consider only 3 elements or less, and their minimum number is a local minimum.

Answer 7

I answer that this is a homework question, so I answer accordingly. You should get a starting position if you are looking for a local minimum, because you need a link for what is "local". If the item on the left is smaller than this item, go to that item and try again. Otherwise, if the item on the right is smaller than the current one, go right and try again. Otherwise, the current item is a local minimum.

EDIT: after I read the question, a requirement for O (log n) was added. I will think of a solution that satisfies this requirement.

Another EDIT: I don't think this is possible in O (log n) time requirement for an unsorted array, because there is no way to split the problem in half. On the other hand, there is a trivial solution O (1) for a sorted array :)