Algorithm: Find peak in a circle

问题:

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.

回答1:

Here's a recursive O(log n) algorithm.

Suppose we have an array of numbers, and we know that the middle number of that segment is no smaller than the endpoints:

A[i] <= A[m] >= A[j]

for i,j indexes into an array, and m=(i+j)/2. Examine the elements midway between the endpoints and the midpoint, i.e. those at indexes x=(3*i+j)/4 and y=(i+3*j)/4. If A[x]>=A[m], then recurse on the interval [i,m]. If A[y]>=A[m], then recurse on the interval [m,j]. Otherwise, recurse on the interval [x,y].

In every case, we maintain the invariant on the interval above. Eventually we get to an interval of size 2 which means we've found a peak (which will be A[m]).

To convert the circle to an array, take 3 equidistant samples and orient yourself so that the largest (or one tied for the largest) is in the middle of the interval and the other two points are the endpoints. The running time is O(log n) because each interval is half the size of the previous one.

I've glossed over the problem of how to round when computing the indexes, but I think you could work that out successfully.

回答2:

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

回答3:

When you say "arranged in a circle", you mean like in a circular linked list or something? From the way you describe the data set, it sounds like these integers are completely unordered, and there's no way to look at N integers and come to any kind of conclusion about any of the others. If that's the case, then the brute-force solution is the only possible one.

Edit:

Well, if you're not concerned with worst-case time, there are slightly more efficient ways to do it. The naive approach would be to look at N_i, N_i-1, and N_i+1 to see if Ni is a peak, then repeat, but you can do a little better.

While not done
    If N[i] < N[i+1]
        i++
    Else
        If N[i]>N[i-1]
            Done
        Else
            i+=2

(Well, not quite that, because you have to deal with the case where N[i]=N[i+1]. But something very similar.)

That will at least keep you from comparing N_i to N_i+1, adding 1 to i, and then redundantly comparing N_i to N_i-1. It's a distinctly marginal gain, though. You're still marching through the numbers, but there's no way around that; jumping blindly is unhelpful, and there's no way to look ahead without taking just as long as doing the actual work would be.