在数组中查找局部最小值 [英] Find local minima in an array

问题描述

给定一个整数数组，找到局部最小值.如果 A[i-1] > A[i] 且 A[i] <; 则元素 A[i] 被定义为局部最小值.A[i+1] 其中 i = 1...n-2.在边界元素的情况下，数字必须刚好小于它的相邻数字.

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.

我知道如果只有一个局部最小值，那么我们可以用修改后的二分搜索来解决.但是如果知道数组中存在多个局部极小值，能否在O(log n)时间内求解?

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?

推荐答案

如果不能保证数组元素是不同的，那么就不可能在 O(log n) 时间内做到这一点.原因如下:假设您有一个数组，其中所有 n > 1 值都相同.在这种情况下，没有一个元素可以是局部最小值，因为没有元素小于它的邻居.但是，为了确定所有值都相同，您必须查看所有数组元素，这需要 O(n) 时间.如果使用的时间少于 O(n)，则不一定能查看所有数组元素.

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.

另一方面，如果保证数组元素是不同的，您可以使用以下观察在 O(log n) 时间内解决这个问题:

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. 如果只有一个元素，则保证是局部最小值.
2. 如果有多个元素，看中间的元素.如果它是本地最小值，那么您就完成了.否则，它旁边的元素中至少有一个必须小于它.现在，想象一下，如果您从较小的元素之一开始，并在远离中间元素的方向上逐渐移向阵列的末端之一，会发生什么.在每一步，要么下一个元素小于前一个元素，要么会更大.最终，您要么以这种方式到达数组的末尾，要么到达局部最小值.请注意，这意味着您可以这样做以找到局部最小值.但是，我们实际上不会这样做.相反，我们将使用这样一个事实，即数组的这一半中将存在局部最小值作为丢弃一半数组的理由.在剩下的部分，我们可以保证找到局部最小值.

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. 如果只有一个数组元素，则为局部最小值.
2. 如果有两个数组元素，请检查每个元素.一个必须是当地最低限度.
3. 否则，查看数组的中间元素.如果它是局部最小值，则返回它.否则，至少有一个相邻的值必须小于这个值.在包含该较小元素的数组的一半(但不是中间)中递归.

注意这里有递归关系

T(1) ≤1

T(2) ≤1

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

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

使用主定理，您可以证明该算法按要求在 O(log n) 时间内运行.

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

希望这有帮助！

另请注意，此算法仅在数组的边小于相邻元素的情况下算作局部最小值时才有效.

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.

这篇关于在数组中查找局部最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！