找到递增然后递减列表的最大值和最小值

Question

我试过用谷歌搜索这个问题，但没有取得多大成功……我确定这个问题或类似问题有一个技术名称，但我似乎找不到答案。

给定一个L严格递增然后严格递减的整数列表，找出该列表的最大值和最小值。

因此，例如，L可能是{1 2 3 4 5 4 3 2}或{2 4 5 7 3}。

为了找到最小值，我说最小的整数必须是左端点或右端点，所以只需比较端点，然后返回最小的一个，给出恒定时间。

为了找到最大值，我基本上建议使用递归二分搜索来找到L[x]满足L[x] > L[x-1]和的点L[x] > L[x+1]，给出摊销的 lg(n) 时间。他似乎并不喜欢这个答案，而且对我来说这似乎很天真，所以我想知道我是否遗漏了什么。

谢谢您的帮助！

编辑：

我在python中的解决方案：

def Max(L):
    n = len(L)-1
    if n == 0:
        return L[0]

    if L[n/2] > L[n/2 - 1] and L[n/2] > L[n/2 + 1]:
        return L[n/2]
    elif L[n/2] < L[n/2 + 1]:
        return Max(L[n/2:])
    else:
        return Max(L[:n/2])  

Answer 1

好吧，查了一下，你有两个选择。更简单的一种是三元搜索。 它的基本要点是，您找到两个数字 1/3 (x) 和 2/3 (y)。如果 x < y，则最大值不能在前三分之一。如果 x > y，则不能在最后三分之一。将它与对基本情况的简单检查结合起来，你就得到了一个递归算法。

现在，它仍然是 O(log(n))，所以每次调用有一半的比较，但只有 2/3 的消除，你真的从 2*log(base 2)(n) 比较到 2*log(基数 3)(n) 比较。从理论上讲，它们是等效的。实际上，您获得的收益并不多，除非您没有随机访问权限，例如，对于某个函数。

更复杂的是斐波那契搜索。 另请参见此处。 它类似于三元搜索，不同之处在于它不是只选择 1/3 和 2/3 作为断点，而是一个涉及斐波那契数列的奇特过程。它仍然是 O(log(n))，因此除非您没有直接随机访问，否则可能不值得为实现而头疼。