c - 在单调递增然后递减的序列中找到一个数字

Question

可以在 O(log n) 中找到单调增加然后单调减少的序列中的最大值或最小值。

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

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

在这个例子中，如果我需要查找序列是否包含'2'，我没有任何条件将搜索空间划分为原始搜索空间的一半。在最坏的情况下，它将是 O(n)，因为当我们尝试搜索 2 时，您需要检查两半。

我想知道，如果这个搜索在 O(log n) 时间内完成？

Answer 1

如您所述，您可以在 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)。

Answer 2

我记得对元素按递增然后递减排序的数组的最佳搜索是斐波那契搜索算法。

Answer 3

这是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