在未排序的列表中查找序列

So, I am given an unsorted list A = (a₁, a₂, ..., a_n) with n distinct elements. My goal here is to find the middle index i (1 <= i <= n) of a sequence where a_i-1 < a_i and a_i > a_i+1. The algorithm should run in O(log(n)) worst case. It is also given that a₀ = a_n+1 = -inf.

所以基本上我需要找到一个被比自身更小的数字包围的索引，例如{1,5,3}，其中1和3小于5。

Example:

输入：A = {1,2,4,5,3,7,6}

输出：4（因为序列为 {4, 5, 3}）

如果最坏情况是 O(n)，那么这个算法将非常简单，其中一个简单的 for 循环可以检查该序列，但我很难接受它需要运行最坏情况 O(log (n))。

首先，请注意，如果您有三个元素a_i, a_j, a_k with i<j<k and a_j > a_i and a_j > a_k，那么之间必定存在一个峰值i and k。证明很简单：介于两者之间的最大值a_i and a_k必须是峰值，并且不能是任一端点。

您可以使用此观察结果在对数时间内解决问题。

我们将保留三个值：x, y, z这样x<y<z and a_y > a_x and a_y > a_z。一开始，初始化x, y, z to 0, (n+1)/2, n+1。 （条件成立，因为a_0 = a_(n+1) = -inf).

现在考虑三元组(x, (x+y)/2, y), ((x+y)/2, y, (y+z)/2), (y, (y+z)/2, z))。这些三元组之一可以作为我们的下一个(x, y, z)。 （证明很简单，但我把它留给你）。

这个过程将每次搜索的范围减半，当我们缩小到一个很小的间隔时（比如z-x < 5），此时峰值最多为 1 或 2 个元素。