假设我有一个 0<=i<=n-1 的数组 a[i]。我可以使用复杂度为 O(log n) 的算法找到 i 满足 1<=i<=n-2, a[i]<=a[i+1] 和 a[i]<=a[i -1]？也就是说，我可以在对数时间内找到局部最小值吗？
注意：我将问题（已更改多次）编辑为可以合理回答的问题。我删除了早期版本中出现的奇怪的结束条件，因为这个版本更简单，但不失一般性。
问问题
7861 次
7 回答
6
首先，我们需要考虑如何定义局部最小值：
a[i] < a[i-1] and a[i] < a[i+1]
从这种情况下，我们看到如果我们在 X/Y 图上绘制数组（X=index，Y=value），局部最小值将位于谷底。因此，为了确保存在局部最小值，我们必须保证存在斜率符号的变化（从减小到增大）。
如果您知道某个范围的端点斜率行为，您就知道其中是否存在局部最小值。此外，您的数组必须具有从 a[0] 到 a[1] 减小斜率符号并将斜率符号从 a[n-1] 增加到 a[n] 的行为，否则问题很简单。考虑：
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
我想这对你完成方法应该是足够的启发。
请注意，扩展此方法仅适用于唯一值，例如全为 1 的数组，除非您进行一些边缘情况检测，否则它不会有 O(log n) 运行时间。
于 2012-08-03T21:53:49.633 回答
3
除非您的数组有其他约束，否则如果没有（至少）线性时间预处理，您将无法在 O(log n) 中找到局部最小值，因为在最坏的情况下，您需要检查数组中的每个元素。不难正式证明这个陈述，其思想是构造这样的数组，对于每种扫描方法，该方法将在构造数组上以线性时间起作用。
例如，假设您正在n从头到尾对大小数组进行简单扫描：如果您的最小值位于n-1第 -th 位置，那么您只会在n-1迭代后发现它，即O(n)
于 2012-08-03T21:41:05.543 回答
1
它通过类似于 O(log n) 中的二进制搜索方法来解决，但仅在数组中有一个局部最小值和不同数字的情况下。您的数组必须类似于以下内容：
8 5 4 3 [1] 2 6 9
一是这里的局部最小值。
检查界限。如果 a[0] < a[1]，则 a[1] 是局部最小值。如果 a[n-1] > a[n]，a[n] 是局部最小值。如果这些条件都不成立 - 开始划分：
检查 a[n/2]，如果 a[n/2] > a[n/2 + 1] 则在数组右侧的局部最小值，否则在左侧。之后递归解决问题。
于 2012-08-03T21:53:53.453 回答
0
我无法反驳这个解决方案的工作原理，所以如果有人可以，我会很高兴。
考虑从 1 到 n 索引的数组“a”。
low = 1
high = n
mid = (low + high)/2
在不失一般性的情况下，我将假设数组值是不同的。所以，在中间， a[mid - 1], a[mid], a[mid + 1] 可以是：
Case 1:
/\
Case 2:
\/
Case 3:
/
/
Case 4:
\
\
Case 5(boundary):
/
Case 6(boundary):
\
&m = 中
可以使用 if 条件检查每种情况，如下所示：
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]
我也将忽略解释边界情况：
第二种情况是 a[m] 是局部最小值的理想情况
第三种情况：
总是有一个局部最小值在左边，所以，设置 h = m - 1 并继续
第四种情况：
右边总是有一个局部最小值，所以，l = m + 1 并继续
对于第一种情况，我可以朝任何一个方向前进：我相信这是可行的，因为您减少正在考虑的段的唯一时间是当您确定减少的段中有局部最小值时，因此您搜索的段将始终具有一些局部最小值。
注意：这仅适用于找到单个局部最小值，而不是每个局部最小值。后一种情况需要 O(n) ，因为您肯定必须至少查看整个数组一次。
于 2014-02-15T06:39:06.587 回答
0
这个问题可以O(logn)通过使用一种二分搜索来解决。
这个技巧在http://www.dsalgo.com/2013/03/find-local-minima-in-array.html中有很好的解释。该网站提供了递归实现。
我实际上想出了另一个迭代实现，如下所示。
#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;
}
输出：Local minima: 7
于 2015-10-04T05:25:43.223 回答
-1
编辑：仅当局部最小值由“<=”定义时才有效，而不是“<”。但是，使用“<”没有解决方案。因此，我将把它保留在这里，并注意它不能解决 OP 的（无法解决的）问题。
如果至少存在一个局部最小值，则以下分治法应该在 O(log n) 中找到一个局部最小值。
- 考虑第一个、最后一个和中间元素（我们称它们为 A、B、C）。
- 如果 A 是三个中最小的，则继续数组的前半部分。
- 否则，如果 C 是三个中最小的，则继续数组的后半部分。
- 否则，（即 B 是三个中最小的一个），检查前半部分 (D) 的中间元素是否低于 B，在这种情况下使用左半部分。
- 否则，检查右半部分 (E) 的中间元素是否低于 B，在这种情况下使用后半部分。
- 否则，继续从 D 到 E 的元素（其中 B 位于中间）。
在每种情况下 2. - 6. 您继续使用在左侧和右侧具有较高元素的元素（尽管不一定直接），或者在边界处。每次要考虑的元素数量减半，所以它是 O(log n)。最后，您只考虑 3 个或更少的元素，其中的最小数量是局部最小值。
于 2012-08-03T22:00:19.567 回答
-2
我假设这是一个家庭作业问题，所以我回答得当。如果您正在搜索局部最小值，则必须给您一个起始位置，因为您需要参考什么是“局部”。如果左边的元素小于该元素，则转到该元素并重试。否则，如果右侧的元素小于当前元素，则向右移动并重试。否则，当前元素是局部最小值。
编辑：在我阅读问题后添加了对 O(log n) 时间的要求。我将考虑满足此要求的解决方案。
另一个编辑：我认为这在未排序数组的 O(log n) 时间要求中是不可能的，因为没有办法将问题分成两半。另一方面，排序数组有一个简单的 O(1) 解决方案:)
于 2012-08-03T21:39:15.983 回答