algorithm - 在最多包含 40 亿个整数的未排序数组中查找缺失的 32 位整数

Question

这是 problem在 Programming pearls 中描述。我无法理解作者描述的二进制搜索方法。任何人都可以帮助详细说明吗？谢谢。

编辑:我可以大致理解二进制搜索。我只是不明白如何在这种特殊情况下应用二进制搜索。如何判断缺失的数字是否在某个范围内，以便我们选择另一个。英语不是我的母语，这是我无法很好地理解作者的原因之一。所以，请使用简单的英语:)

编辑:感谢大家的精彩回答和评论!我从解决这个问题中学到的最重要的教训是二分搜索不仅适用于排序数组!

Answer 1

关于 this web site 有更多信息.从那里引用:

“根据表示每个整数的 20 位来查看此二分搜索很有帮助。在算法的第一遍中，我们读取(最多)一百万个输入整数，并将前导零位写入一个磁带和那些前导一位到另一个磁带的磁带。这两个磁带中的一个最多包含 500,000 个整数，因此我们接下来使用该磁带作为当前输入并重复探测过程，但这次是在第二位上。如果原始输入磁带包含 N 个元素，第一遍将读取 N 个整数，第二遍最多读取 N/2，第三遍最多读取 N/4，依此类推，因此总运行时间与 N 成正比。缺少的整数可以通过在磁带上分类然后扫描来找到，但这需要的时间与 N log N 成正比。”

如您所见，这是二分搜索算法的一种变体:将问题分成两部分，然后解决其中较小部分的问题。