如何在只有两类元素的有序数组中快速查找指定元素？
How to quickly search for a specified element in an ordered array consisting of only two types of elements?
题中提到的数组如下：
[1,1,...,1,1,-1,-1,...,-1,-1]
如何快速找到最接近-1的1的索引？
注意：1和-1会同时存在，而且1和-1的数量很大
例如，对于这样的数组：
[1,1,1,1,1,-1,-1,-1]
结果应该是 4。
我能想到的最快的方法是二分查找，有没有更快的方法？
对于当前的数据表示，二分查找是我能想到的最快的方法。当然，您可以在常数时间内缓存和重用结果，因为答案总是相同的。
另一方面，如果将数组的表示更改为一些简单的数字，则可以在常数时间内找到下一个元素。由于数据始终可以映射为二进制值，因此您可以将整个数组减少为 2 个数字。第一个分区的长度和第二个分区的长度。或者整个数组的长度和分区点。这样您就可以在恒定时间内轻松更改两个分区的长度，并可以在恒定时间内访问第二个分区的下一个元素。
当然，改变数组本身的表示是一个对数过程，因为你需要找到分区点。
通过一个简单的信息论论证，仅使用比较，您不可能比 log(n) 更快。因为有 n 种可能的结果，您需要至少收集 log(n) 位信息才能对它们进行编号。
如果您有关于值的统计分布的额外信息，那么也许您可以利用它。但这个要具体情况具体讨论。
题中提到的数组如下：
[1,1,...,1,1,-1,-1,...,-1,-1]
如何快速找到最接近-1的1的索引？
注意：1和-1会同时存在，而且1和-1的数量很大
例如，对于这样的数组：
[1,1,1,1,1,-1,-1,-1]
结果应该是 4。
我能想到的最快的方法是二分查找，有没有更快的方法？
对于当前的数据表示，二分查找是我能想到的最快的方法。当然，您可以在常数时间内缓存和重用结果，因为答案总是相同的。
另一方面，如果将数组的表示更改为一些简单的数字，则可以在常数时间内找到下一个元素。由于数据始终可以映射为二进制值，因此您可以将整个数组减少为 2 个数字。第一个分区的长度和第二个分区的长度。或者整个数组的长度和分区点。这样您就可以在恒定时间内轻松更改两个分区的长度，并可以在恒定时间内访问第二个分区的下一个元素。
当然，改变数组本身的表示是一个对数过程，因为你需要找到分区点。
通过一个简单的信息论论证，仅使用比较，您不可能比 log(n) 更快。因为有 n 种可能的结果，您需要至少收集 log(n) 位信息才能对它们进行编号。
如果您有关于值的统计分布的额外信息，那么也许您可以利用它。但这个要具体情况具体讨论。