Algorithm: Find peak in a circle

Question

Given n integers, arranged in a circle, show an efficient algorithm that can find one peak. A peak is a number that is not less than the two numbers next to it.

One way is to go through all the integers and check each one to see whether it is a peak. That yields O(n) time. It seems like there should be some way to divide and conquer to be more efficient though.

Answer 1

EDIT

Well, Keith Randall proved me wrong. :)

Here's Keith's solution implemented in 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