算法:在圆圈中找到峰值

Question

给定 n 个整数，排列成一个圆圈，展示一种可以找到一个峰的高效算法。一个峰值是一个不小于它旁边的两个数字的数字。

一种方法是遍历所有整数并检查每个整数是否为峰值。这产生了 O(n) 时间。似乎应该有一些分而治之的方法来提高效率。

Answer 1

编辑

好吧，Keith Randall 证明我错了。 :)

这是用 Python 实现的 Keith 解决方案:

def findPeak(aBase):
    N = len(aBase)
    def a(i): return aBase[i % N]

    i = 0
    j = N / 3
    k = (2 * N) / 3
    if a(j) >= a(i) and a(j) >= a(k)
        lo, candidate, hi = i, j, k
    elif a(k) >= a(j) and a(k) >= a(i):
        lo, candidate, hi = j, k, i + N
    else:
        lo, candidate, hi = k, i + N, j + N


    # Loop invariants:
    # a(lo) <= a(candidate)
    # a(hi) <= a(candidate)

    while lo < candidate - 1 or candidate < hi - 1:
        checkRight = True
        if lo < candidate - 1:
            mid = (lo + candidate) / 2
            if a(mid) >= a(candidate):
                hi = candidate
                candidate = mid
                checkRight = False
            else:
                lo = mid
        if checkRight and candidate < hi - 1:
            mid = (candidate + hi) / 2
            if a(mid) >= a(candidate):
                lo = candidate
                candidate = mid
            else:
                hi = mid

    return candidate % N