给定一个未排序的二进制数组，计算 1 的数量，其中只允许检查整个子数组是否全为零

Question

给定一个未排序的二进制数组a，唯一允许的操作是all_zeros(a)，如果数组的所有元素都为0，则返回True。
all_zeros(a)的复杂度为o(len(a)) + large overhead constant

我想找到所有包含1的索引，在all_zero中尽可能少的运行一个合理的子问题是假设1的数量是"多";(例如，x100~x1000)小于0的个数

---

理论上，这可以简单地通过迭代数组元素来解决，并测试all_zeros([element]).
在实践中，开销常数迫使我们尽可能批量地工作。我们不能假设知道数组中1的比例，但如果某些算法需要这些知识，请务必分享。

我正在寻找一个概念性的解决方案，因此我没有指定开销常数与all_zeros的计算时间之间的比率。

请注意，我正在寻找一个平均情况解决方案，而不是最坏情况的解决方案。
现在需要定义1和0的概率分布，但我试图将其保持在一个较高的水平，我不会深入讨论细节，同时仍然保持这个可回答的。
可能有一个最佳情况解决方案，它总是得到最小的开销。如果有，我们会接受的。

Answer 1

我会检查大块，如果它们不为零，只尝试较小的块。根据15和"大开销常数"的比例，我会选择一个合适的起始大小。

下面是如何检查(通过示例) 的想法数据:(空格仅用于可读性)

00001110 00100001 00100000 01000000 00000000 00000000 00000101 01010000
1. xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
-> both checked intervalls are non-zero -> half them
2. xxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXX xxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXX
non-zero           non-zero          zero              non-zero
3. xxxxxxxx XXXXXXXX xxxxxxxx XXXXXXXX                   xxxxxxxx XXXXXXXX
n-z      n-z      n-z      n-z                        n-z      n-z   
4. xxxxXXXX xxxxXXXX xxxxXXXX xxxxXXXX                   xxxxXXXX xxxxXXXX
zero n-z n-z n-z  n-z zero n-z zero                   zero n-z n-z zero
5.     xxXX xxXXxxXX xxXX     xxXX                           xxXX xxXX 
...

我希望这个想法是清楚的。但是，我强烈建议配置从哪个块大小开始，以及何时切换为单元素块。

Answer 2

如果all_zeros(a)对某些子数组返回false，则可以在该子数组中进行二进制搜索以查找第一个1的位置。这个过程不会告诉你任何跟在1后面的元素，所以你要从1后面重新开始。

问题是初始查询的大小。如果每个查询返回true的概率为50%，则执行的查询总数最少。如果你的初始查询有50%的机会找到1，那么二分查找中的所有查询也有50%的机会，并且每个1的总成本是log₂L + 1个查询，如果15个槽平均间隔L个槽。

如果L的长度是应有长度的两倍，或者是应有长度的一半，那么每1个查询的成本就会增加1个，当15相距很远时，这是一个相当小的代价。

所以一个不需要知道1s频率的很好的算法是:

1. 设置L=128，例如。这是1个频率的先验估计。
2. 检查前L个元素。如果全部为零，则将L乘以2并继续处理数组的其余部分。
3. 否则，如果是>1、二进制查找查找第一个1的位置，并在第一个1之后继续查找数组的其余部分。

总成本将是log₂L + some_small_number每1查询，如果1是随机分布的，我认为这是最坏的情况。