这是问题编程珍珠。我不明白的作者descrbied二进制搜索方法。任何一个可以帮助详细点吗？谢谢你。

This is the problem described in Programming pearls. I can not understand binary search method descrbied by the author. Can any one helps to elaborate? Thanks.

编辑： 我可以理解一般的二进制搜索。我只是不明白如何在这种特殊情况下使用二进制搜索。如何确定丢失的号码是与否在一定范围内，使我们可以选择另外一个。英语不是我的母语，这是一个原因，我无法理解作者很好。因此，用简单的英语，请：）

I can understand binary search in general. I just can not understand how to apply binary search in this special case. How to decide the missing number is in or not in some range so that we can choose another. English is not my native language, that is one reason I can not understand the author well. So, use plain english please:)

编辑：谢谢大家对你的伟大的回答和评论！最重要的教训我从解决这个问题，倚为二进制搜索不仅适用于排序数组！

Thank you all for your great answer and comments ! The most important lesson I leant from solving this question is Binary search applies not only on sorted array!

推荐答案

有上的这个网站。从那里引用：

这是有帮助的，以查看的20比特重新present每一整数计算，这二进制搜索。在该算法的第一阶段我们读（最多）百万输入整数，写那些具有前导零位到一个磁带和那些具有领先一个位到另一个磁带。其中的一个两个带含有至多500000的整数，因此，我们接下来使用磁带作为当前输入，并重复所述探针的过程，但这次在第二位，如果原始输入磁带包含N个元素，第一遍将读取N个整数中，第二阶段最多N / 2时，第三通最多N / 4，等等，所以总运行时间为N成正比的缺失整数可以通过在磁带上，然后扫描排序可以找到，但这需要时间比例为N为log N。

"It is helpful to view this binary search in terms of the twenty bits that represent each integer. In the first pass of the algorithm we read the (at most) one million input integers and write those with a leading zero bit to one tape and those with a leading one bit to another tape. One of those two tapes contains at most 500,000 integers, so we next use that tape as the current input and repeat the probe process, but this time on the second bit. If the original input tape contains N elements, the first pass will read N integers, the second pass at most N/2, the third pass at most N/4, and so on, so the total running time is proportional to N. The missing integer could be found by sorting on tape and then scanning, but that would require time proportional to N log N."

正如你所看到的，这是对二进制搜索算法的变化：分化问题分为两部分，并解决问题的小作品之一

As you can see, this is a variation on the binary search algorithm: divide the problem into two pieces and solve the problem for one of the smaller pieces.