我有一个大小为n的数组arr，它以随机顺序包含1到n的整数；例如，它可能是arr = [4 5 3 6 2 1]。
对于arr中的每个元素e，我需要找到小于e的最接近的元素k（就位置而言是“最接近的”，而不是值；因此在上面的例子中，5比6更接近3。）如果两个方向上都有同样接近的较小元素（如上面例子中的6，其近邻都小于它），则它不是选择这些元素中的哪一个。
因此，对于上面的例子，arr = [4 5 3 6 2 1]，一个有效的结果是[3 3 2 2 1 NIL]。
我知道一个O（n）算法来解决这个问题；它通过维护一个堆栈来找到每个元素左右最近的较小元素。
但令人惊讶的是，一个简单的线性双向搜索比那个算法执行得更好，尽管在我看来在最坏的情况下是O（n2）：
for i = 1 to N
right = i + 1
left = i - 1
while (left > 0 && right <= n)
// ...find the closest element that is smaller than arr[i] and break while loop
上述情况最复杂的情况是什么？我说的是o（n2）对吗？
最佳答案
这是最坏的情况（n logn）时间（假设您实现了Daniel上面提到的修复-您需要确保您可以在每个方向上一直扫描到最后）。
首先，观察如果两个元素a和b是邻居，则a通过扩展，至少一半的数组元素只需要1的搜索距离。
类似地，如果四个元素[a，b，c，d]都在一行中，那么其中一个元素小于另外三个元素。因此，这些元素中至少有三个需要最多3个搜索距离如上所述，其中的两个实际上只需要1的搜索距离，所以实际上这意味着两个搜索距离为1，而第三个搜索距离最多为3。总搜索距离最多为2.1+1.3+（n−1）。
我们可以继续这个逻辑来增加2K长度：我们最多有2K-1·（21-1）+2K-2·（22-1）+2K-3·（23-1）++（n-1）。
如果n是2的幂，那么我们可以写为2k，总搜索距离最多为：
2K-1·（21-1）+2K-2·（22-1）+2K-3·（23-1）++20·（2K-1）=
=（2K-2K-1）+（2K-2K-2）+（2K-2K-3）++（2K-20）
=K·2K−2K+1
=n对数n−对数n+1
（如果n不是2的幂，那么我们可以通过附加值n+1、n+2等来获得一个稍大的数组，直到我们有2的幂，并且观察到得到的总搜索距离小于2n log 2n，它仍然在Θ（n logn）。）
当然，以上只是设定了一个上限（O而不是Θ）；但我认为这说明了如何真正实现最坏的情况：我们希望以两种方式的幂形式，将最小的数字尽可能分散开来例如，我们可以“展开”这样的列表：
1 2
1 3 2 4
1 5 3 6 2 7 4 8
如上所述，总搜索距离为7+1+2+1+4+1+2+1=17=3·8-8+1。