c - 搜索缺失号码 - 简单示例

Question

关于在 C 中搜索算法和复杂性的小任务。我只是想确保我是正确的。

我有 n 个从 1 到 n+1 的自然数，从小到大排序，我需要找到缺失的那个。例如:1 2 3 5 6 7 8 9 10 11 - 答案:4

最快和最简单的答案是做一个循环并检查每个数字和它后面的数字。在最坏的情况下，其复杂度为 O(n)。

我想也许我遗漏了一些东西，我可以使用二进制搜索找到它。任何人都可以在那个简单的例子中考虑更有效的算法吗？比如 O(log(n)) 之类的？

Answer 1

显然有两个答案:

如果你的问题是纯理论问题，尤其是大n ，你会做类似二进制搜索的事情，并检查最后两个边界之间的中间是否实际上是 (upper-lower)/2 .

但是，如果这是一个实际问题，对于执行 C 中编写的程序的现代系统并由现代高度优化的编译器编译为 n << 10000 ，我认为线性搜索方法要快得多，只是因为它可以很容易地矢量化。事实上，现代 CPU 有执行指令，例如每一个

1. 一次减去 4 个整数，减去另外四个整数，
2. 将结果与 [4 4 4 4] 进行比较
3. 将计数器增加 4，
4. 加载接下来的 4 个整数，

等等，这非常巧妙地适用于 CPU 和内存 Controller 预取线性内存这一事实，因此，以对数递减的步长大小跳跃可以产生巨大的性能影响。

所以:对于大n ，在线性搜索不切实际的地方，选择二进制搜索方法；对于 n在有疑问的地方，进行线性搜索。如果您不仅具有 SIMD 功能而且还具有多个内核，那么您将希望拆分您的问题。如果您的问题实际上不是exactly 1 缺失数字，您可能想要使用完全不同的方法......整个O(n)业务通常更像是纯粹可用于理论构造的基准，除非差异非常大，否则很少是在实际实现中选择特定算法的唯一原因。