arrays - 如何以最有效的方式在大小为 100 的整数数组中找到 0，其中 99 个元素为 1，只有一个元素为 0

Question

我需要找到大小为 100 的整数数组 A 的位置(或索引)say i，使得 A[i]=0。数组A的99个元素都是1，只有一个元素是0。我想用最高效的方式解决这个问题。(所以没有一个一个元素比较)。

Answer 1

其他人已经回答了基本问题 - 您必须检查所有条目，或者至少检查直到找到零为止。这将是 99 次比较的最坏情况。 (因为如果前 99 个是 1 那么你已经知道最后一个条目必须是零，所以你不需要检查它)

这些答案中可能存在的缺陷是假设您一次只能检查一个条目。

实际上，我们可能会使用直接内存访问来一次比较多个整数。 (例如，如果您的“整数”是 32 位，那么具有 SIMD 指令的处理器可以一次比较 128 位，以查看一组 4 个值中是否有任何条目包含零 - 这将使您的蛮力扫描速度快将近 4 倍。显然，整数越小，您可以一次比较的条目就越多。

但这不是最佳解决方案。如果您可以指示这些值的存储，那么您可以将整个“数组”存储为仅 100 位的二进制位(0/1 值)(最简单的方法是使用两个 64 位整数(128 位)并用 1 填充备用的 28 位)，然后您可以进行“二进制分割”以查找数据。

本质上，“二进制分割”的工作原理是将数据分割成两半。一半是全 1，另一半是零。因此，单次比较允许您一次拒绝一半的值。 (你可以做一个比较，因为你的数组的一半将适合 64 位长，所以你可以将它与 0xffffffffffffffff 进行比较，看看它是否全为 1)。然后重复包含零的那一半，再次将其一分为二并确定哪一半包含零……等等。这将始终在 7 次比较中找到零值 - 比单独比较所有 100 个元素要好得多。

这可以进一步优化，因为一旦你降低到一两个字节的级别，你可以简单地在预先计算的查找表中查找字节/字值，以告诉你哪一位是零。这将使算法减少到 4 次比较和 1 次查找(在 64kB 表中)，或 5 次比较和 1 次查找(在 256 字节表中)。

所以在最坏的情况下我们减少到大约 5 次操作。

但是，如果您可以规定数组的存储方式，则只需记下零条目的索引即可“存储”数组。根本不需要存储所有单独的值。这只需要 1 个字节的内存来存储状态，而这个字节已经包含了答案，让您只需 1 个操作(读取存储的值)的成本。