找到一个单数增加然后递减的序列

在O（log n）中可以完成单调增加然后单调减少的序列中的最大值或最小值。找到一个单数增加然后递减的序列

但是，如果我想检查一个数是否存在于这样的序列中，那么这也可以在O（log n）中完成吗？

我不认为这是可能的。考虑这个例子：1 4 5 6 7 10 8 3 2 0.

在这个例子中，如果我需要找出序列是否包含'2'，我没有任何条件将搜索空间分成一半原始的搜索空间。在最坏的情况下，它将是O（n），因为您需要检查两个部分，当我们试图搜索2.我想知道，如果此搜索在O（日志n）时间？

来源

2012-07-18 vamsi

正如你所说的，你可以在O（logn）中找到最大值（及其位置）。然后，您可以在每个部分进行二进制搜索，这也是O（logn）。

在上例中，您在位置5找到最大值10。然后在子序列[0..5]（1，4，5，6，7，10）中执行二进制搜索。由于未找到2，因此您继续在另一部分（10,8,3,2,0）中执行二分查找。

要找到O（logn）中的最大值：看中间的两个元素：7 < 10.所以我们仍处于增长的部分，必须在序列的右半部分查找最大值：（10,8,3,2,0）。看看8和3左边的部分（10,8）。

来源

2012-07-18 07:20:08 Henrik

请问您可以继续上面的例子，在上面的顺序中找到2。并在O（logn） – vamsi 2012-07-18 07:21:36

导出解决方案嗯...这里的问题是在O（logn）中找到最大值。剩下的就像你提到的 – 2012-07-18 07:54:20

@AndyStowAway我认为这是明确的（对OP）。编辑我的答案。 – Henrik 2012-07-18 08:03:33

正如我记得最好的搜索阵列的元素排序增加，然后减少是斐波那契搜索算法。

来源

2017-04-20 17:08:09 Hovo

这是python中的草图。总之，我们的目标是找到一个与增长和减少区域相邻的元素（我们检查两个条件来检查相邻元素）。我们继续像标准二进制搜索一样跳转，直到找到这个元素。希望有所帮助。

def get_max(arr): 
    if len(arr) == 1: 
     return arr[0] 
    if len(arr) in [0,2]: 
     return None 
    left, right = 0, len(arr) - 1 
    while left <= right: 
     mid = (left+right) // 2 
     #increasing region 
     if arr[mid+1] > arr[mid] and arr[mid] > arr[mid-1]: 
      left = mid + 1 
     #decreasing region 
     elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]: 
      right = mid - 1 
     elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]: 
      return arr[mid-1] 
     else: 
      return arr[mid] 
    return -1

来源

2018-01-29 18:21:50

找到一个单数增加然后递减的序列

回答

相关问题