给定未排序的二进制数组，计数为1＆＃x27; s，只能检查整个子阵列是否均为zeros

Question

给定一个未排序的二进制数组，a，唯一允许的操作是all_zeros（a），它返回true如果所有数组的元素为0 。
此all_zeros（a）的复杂性是o（len（a）） +大型开销常数

我想找到所有包含1s，的索引All_zeros 的运行最少 一个合理的子问题是假设1s的数量“大多数”（例如，x100〜x1000）小于0。

---

从理论上讲，这是通过在数组元素上迭代和测试all_zeros（[element]）。
来解决的。
实际上，间接费用恒定迫使我们尽可能大的批量工作。我们不能假设知道数组中1的比率，但是如果某些算法需要该知识，请分享。

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

请注意，我正在寻找平均情况解决方案，而不是为最坏的情况解决方案。
现在，这需要在1和0上定义概率分布，但是我试图将其保持在很高的水平上，而我不会大大介绍细节，同时仍保持此答案。

可能会有一个最佳情况解决方案，这些解决方案始终获得最小开销。如果有一个，它将被接受。

Answer 1

我会检查大块，只有较小的块，如果它们不是零。
根据1s的比率和“大型高架常数”，我会选择合适的开始尺寸。

在这里，如何检查（例如）

数据：（仅用于可读性）

   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的任何元素一无所知，因此您将在那之后重新开始。

问题是要制作最初的查询的大小。如果每个查询返回true的概率为50％，您将进行最少的查询总数。如果您的初始查询有50％的机会找到1，则二进制搜索中的所有查询也将有50％的机会，而总成本 per 1 是log2 < /sub> l + 1查询，如果1s平均分开。

如果L的时间是应有的两倍，那么或一半是应有的时间，那么成本每1查询约1查询，这是1s相距遥远的价格很小。

因此，不需要知道1开始的频率的非常好的算法将是：

1. 设置L = 128。这是1个频率的先验估计值。
2. 检查第一个L元素。如果全部为零，则将L乘以2，然后继续使用该数组的其余部分。
3. 否则，如果是＆gt，则将l除以2； 1，二进制搜索以找到第一个1的位置，并在第一个1之后继续使用阵列的其余部分。

总成本将是log2 l + some_small_small_small_number每1的查询，如果1是随机分布的，我认为这是最坏的情况。