问题中提到的阵列如下：

[1,1,...,1,1,-1,-1,...,-1,-1]

如何快速找到最接近-1的1的索引？

注意：1和-1会同时存在，1和-1的个数很大。

例如，对于这样的阵列：

[1,1,1,1,1,-1,-1,-1]

结果应该是 4。

我能想到的最快的方法是二分查找，有没有更快的方法？

uj5u.com热心网友回复：

使用当前的资料表示，二进制搜索是我能想到的最快的方法。当然，您可以在恒定时间内快取和重用结果，因为答案总是相同的。

另一方面，如果将阵列的表示更改为一些简单的数字，则可以在恒定时间内找到下一个元素。由于资料始终可以映射到二进制值，因此您可以将整个阵列减少为 2 个数字。第一个磁区的长度和第二个磁区的长度。或者整个阵列的长度和磁区点。这样，您可以在恒定时间内轻松更改两个磁区的长度，并在恒定时间内访问第二个磁区的下一个元素。

当然，更改阵列本身的表示是一个对数程序，因为您需要找到磁区点。

uj5u.com热心网友回复：

通过一个简单的信息论论证，你不能比log(n)只使用比较快。因为有n可能的结果，你需要至少收集log(n)一些信息来对它们进行编号。

如果您有关于值的统计分布的额外信息，那么也许您可以利用它。但这要根据具体情况进行讨论。