算法：找到圆中的峰值

Given n排列成圆圈的整数显示了一种可以找到一个峰值的有效算法。峰值是不小于它旁边的两个数字的数字。

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

EDIT

好吧，基思·兰德尔证明我错了。 :)

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

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