＆QUOT;编程珠玑＆QUOT;二进制搜索帮助 [英] "Programming Pearls" binary search help

问题描述

我似乎无法理解如何做到这一点的工作。

I just can't seem to understand how this would work.

问：
给定包含至多四十亿32位整数中随机顺序顺序文件，找到一个32位整数，不是文件中（和必须有至少一个缺失）

Question:
Given a sequential file that contains at most four billion 32 bit integers in random order, find a 32-bit integer that isn't in the file (and there must be at least one missing)

答：
是有帮助的中的32位，它重新present每一整数术语查看此二进制搜索。在算法的第一个过程中，我们读到了（最多）四十亿输入整数和写那些带前导零位后连续的文件以及与一家领先的一个位到另一个文件。

Answer:
it is helpful to view this binary search in terms of the 32 bits that represent each integer. In the first pass of the algorithm we read the (at most) four billion input integers and write those with a leading zero bit to one sequential file and those with a leading one bit to another file.

其中这些文件包含至多两个十亿整数，所以我们下使用该文件作为当前输入，并重复所述探针的过程，但这次在第二位

One of those files contains at most two billion integer, so we next use that file as the current input and repeat the probe process, but this time on the second bit.

因此​​，通过再次拆分文件遍地（二进制搜索）怎么会变成这样实际上使我丢失的32位整数？

So by splitting the file over and over again (binary search) how would this actually lead me to the missing 32 bit integer?

推荐答案

在每个传递你的下一个阶段将是对你已经编译了两个列表较小。

After each pass your next pass will be on the smaller of the two lists you've compiled.

在某些时候，你必须遇到一个空列表，这将决定你的电话号码。例如，让我们只用3位数字。

At some point, you MUST encounter an empty list and this will determine your number. For example let's just use 3 bit numbers.

000
001
110
100
111

在我们第一遍

000
001

110
100
111

然后我们来看看在第2位，第一个列表，因为它是小于（或等于）第二。 我们将他们分成

Then we look at the 2nd bits in the first list because it is smaller than (or equal to) the second. We would split them into

000
001

empty list

注意如何将开始与 01 文件是空的，这意味着没有开始的号码01 所以 010 和 011 失踪。

notice how the file that would start with 01 is empty, this means that there are no numbers that start with 01 so 010 and 011 are missing.

我们必须最终有失踪名单的原因是因为我们选择了我们的每一次下传的小单。

The reason we must eventually have a missing list is because we are choosing the smaller list for our next pass each time.

这篇关于＆QUOT;编程珠玑＆QUOT;二进制搜索帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！