在未排序的列表中查找序列 [英] Find a sequence in an unsorted list

问题描述

所以，我得到一个未排序的列表A =（a ₁ ，a ₂ ，...，a _n ），其中n不同的元素。我的目标是要找到a _i-1 < i等于1的序列的中间索引i（1< = i< = n）。 a _i 和a _i > a _{i + 1} 。该算法应在O（log（n））最坏的情况下运行。还给出a ₀ = a _{n + 1} = -inf。

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。

So basically i need to find an index surrounded by smaller number than itself, such as {1,5,3}, where 1 and 3 are smaller than 5.

示例：

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

Input: A = {1, 2, 4, 5, 3, 7, 6}

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

Output: 4 (because of the sequence {4, 5, 3})

如果最坏的情况是O（n），则此算法将非常简单，其中一个简单的for循环可以检查该顺序，但是我很难处理它需要运行最坏情况O（log（n））的事实。

This algorithm would be extremly easy if the worst case was to be O(n), where a simple for-loop could check that sequence, but I'm having a hard time with the fact that it needs to run worst case O(log(n)).

推荐答案

首先，请注意，如果您具有三个元素 a_i ， a_j ， a_k 和 i< j< k 和 a_j> a_i 和 a_j> a_k ，那么 i 和 k 之间必须有一个峰值。证明很简单： a_i 和 a_k 之间的最大值必须是峰值，并且不能

First, note that if you have three elements a_i, a_j, a_k with i<j<k and a_j > a_i and a_j > a_k, then there must be a peak between i and k. The proof is easy: the maximum value that lies between a_i and a_k must be a peak, and it can't be either of the endpoints.

您可以使用此观察值以对数时间解决问题。

You can use this observation to solve the problem in logarithmic time.

我们'将保留三个值： x，y，z ，这样 x << y 和 a_y> a_x 和 a_y> a_z 。首先，初始化 x ， y ， z 0，（n + 1）/ 2，n + 1 。 （条件将成立，因为 a_0 = a_（n + 1）= -inf ）。

We'll keep three values: x, y, z such that x<y<z and a_y > a_x and a_y > a_z. At the start, initialize x, y, z to 0, (n+1)/2, n+1. (The conditions will hold, because 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）。 （证明很简单，但我会留给您）。

Now consider the triples (x, (x+y)/2, y), ((x+y)/2, y, (y+z)/2), (y, (y+z)/2, z)). One of these triples can serve as our next (x, y, z). (The proof is easy, but I'll leave it to you).

此过程将每次搜索的范围减半，当我们降低到小间隔（例如 zx <5 ），此时峰值最多为1或2个元素。

This process halves the range searched each time, and we stop when we're down to a small interval (say z-x < 5), at which point the peak is at most 1 or 2 elements.

这篇关于在未排序的列表中查找序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！