algorithm - 找到先增加后减少列表的最大值和最小值

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

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

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

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