5

我很难解决这个问题。

A[1..n] is an array of real numbers which is partially sorted:
There are some p,q  (1 <= p <= q <=n) so:
A[1] <= ... <= A[p]
A[p] >= ... >= A[q]
A[q] <= ... <= A[n]

How can we find a value in this array in O(lgn)?
(You can assume that the value exists in the array)
4

3 回答 3

7

进行 3 次二进制搜索：从 1 到 p、p 到 q 和 q 到 n。复杂度仍然是 O(logn)。

由于我们不知道 p 和 q：

您无法在登录时间内解决此问题。假设您有一个排序的正数列表，其中混合了一个零（p+1=q 和 A[q]=0）。这种情况满足你提到的所有标准。现在，找到那个零的位置的问题不能在 sub O(n) 时间内解决。因此，您的问题无法在 O(logn) 时间内解决。

于 2013-07-08T23:05:41.293 回答
0

尽管已经指出了“埋零”最坏的情况，但我仍然建议实施一种通常可以加快速度的算法，具体取决于 p,q。例如，假设您有 n 个数字，并且每个递增和递减区域的大小至少为 k。然后，如果您检查数组中的 2^m 个元素，包括第一个和最后一个元素以及尽可能等距的其余元素，从 m=2 开始，然后将 m 迭代增加 1，最终您将达到 m从您检查的 2^m 个元素中从左到右找到 3 对连续元素 (A,B),(C,D),(E,F) 满足 A < B, C > D , E < F（某些对可能共享元素）。如果我粗略的计算是正确的，那么最坏的情况 m 你需要实现这一点将让你检查不超过 4n/k 个元素，所以例如如果 k=100 你比检查所有 n 个元素要快得多。然后你知道 A 之前的所有东西和 F 之后的所有东西都是递增序列，你可以对它们进行二进制搜索。现在，如果 m 足够大，您至少检查了 sqrt(n) 个元素，那么您可以通过在 A 和 F 之间进行蛮力搜索来完成，总运行时间将为 O(n/k + sqrt(n ））。另一方面，如果最后的 m 让你检查的元素少于 sqrt(n)，那么你可以进一步增加 m，直到你检查了 sqrt(n) 元素。那么就会有2对满足A < B, C > D的连续被检查元素(A,B),(C,D)，也会有2对连续被检查元素(W,X),(Y ,Z) 稍后在满足 W > X 的数组中，Y < Z。那么 A 之前的一切都在增加，D 和 W 之间的一切都在减少，Z 之后的一切都在增加。因此，您可以对数组中的这 3 个区域进行二分搜索。您尚未完全搜索的数组的剩余部分大小为 O(sqrt(n))，因此您可以使用蛮力搜索未检查的区域，总运行时间为 O(sqrt(n))。因此，边界 O(n/k + sqrt(n)) 通常成立。我觉得这是最坏情况下的最佳选择，但我没有证据。所以你可以使用蛮力搜索未检查的区域，总运行时间为 O(sqrt(n))。因此，边界 O(n/k + sqrt(n)) 通常成立。我觉得这是最坏情况下的最佳选择，但我没有证据。所以你可以使用蛮力搜索未检查的区域，总运行时间为 O(sqrt(n))。因此，边界 O(n/k + sqrt(n)) 通常成立。我觉得这是最坏情况下的最佳选择，但我没有证据。

于 2013-07-12T17:34:45.043 回答
0

它可以在 O(log 2 n) 中解决。

  1. 如果在中点斜率正在减小，我们就在p..q范围内。
  2. 如果在中点斜率增加，我们要么在范围内，要么1..p在q..n范围内。
    • 1.. mid point在和范围内执行二分搜索mid point..n以寻找斜率减小的值。它只会在其中一个范围内找到。现在我们知道中点位于哪个1..p和子范围中。q..n
  3. 对具有峰值的子范围重复 (1) 的过程，直到达到该p..q范围。
  4. 通过应用 分治算法中的算法来查找子范围中的峰值，该算法应用于查找数组中的峰值。
  5. 在 1..p、p..q、q..n 范围内执行 3 次二进制搜索。

==> 总体复杂度为 O(log 2 n)。

于 2013-07-12T17:50:46.690 回答