鉴于n整数，安排在一个圆圈，显示出一个高效的算法，可以找到一个高峰。 峰值是一个数字，是不是比它旁边的两个数字少。
一种方法是通过所有的整数和检查每一个，看它是否是一个高峰。 其产生O(n)时间。 好像应该有某种方式来分而治之更有效率，虽然。
Answer 1:
下面是一个递归O(log n)算法。
假设我们有一个数字数组，而我们知道，该段的中间数不大于端点较小：
A[i] <= A[m] >= A[j]
为I，J索引到一个数组，并且m=(i+j)/2 。 检查中途端点和中间点，即，那些之间的元件的索引x=(3*i+j)/4和y=(i+3*j)/4 。 如果A[x]>=A[m] ，则递归在区间[i,m] 如果A[y]>=A[m] ，则递归在区间[m,j] 。 否则，递归在区间[x,y]
在任何情况下，我们维持对上述区间不变。 最终我们得到大小为2的间隔，这意味着我们已经找到的峰值（这将是A[m] ）。
到圆转换为数组，取3周等距离的样品和确定自己的方位，以使最大（或一个并列最大）是在间隔的中间，另两个点的端点。 运行时间是O(log n) ，因为每个间隔为前一个的大小的一半。
我已经掩盖了如何计算索引时四舍五入问题，但我认为你可以工作了这一点成功。
Answer 2:
编辑
好吧，基思·兰德尔证明我错了。 :)
下面是用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
Answer 3:
当你说“排成一圈”，你的意思是像一个循环链表还是什么？ 从你描述的数据集的方式，这听起来像这些整数是完全无序的，而且也没有办法看N个整数，来到任何形式任何其他的结论。 如果是这样的话，那么蛮力解决方案是唯一可能的一个。
编辑：
好吧，如果你不最坏情况下的时间而言，有稍微更有效的方式来做到这一点。 天真的办法是看N I，N I-1和N I + 1，看是否Ni是一个高峰，然后重复，但你可以做的更好一点。
While not done
If N[i] < N[i+1]
i++
Else
If N[i]>N[i-1]
Done
Else
i+=2
（好吧，没有想象中的，因为你必须要处理的情况下N [1] = N [I + 1]，但非常类似的东西。）
这将至少让你从比较N I到N + 1，加1到我，然后冗余比较N I到N I-1。 这是一个明显的边际效益，但。 你仍然可以通过数字进发，但有周围没有办法; 跳跃是一味无益，而且也没有办法向前看而不采取公正，只要做实际的工作会。
文章来源: Algorithm: Find peak in a circle
